#include <bits/stdc++.h>

#define el '\n'
#define fi first
#define sec second
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
#define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)

using namespace std;

const long long LLNF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int MAX_N = 2e5;
const int MAX_A = 1e6;

vector<int> pos[MAX_A + 5]; // Lưu vị trí xuất hiện của từng số
pii best[MAX_A + 5][2]; // Mảng best, best[d][0] là tốt nhất, best[d][1] là tốt nhì
int omega[MAX_A + 5]; // Mảng lưu Ω của từng số
int spf[MAX_A + 5]; // Mảng spf để phân tích ra thừa số nguyên tố rồi sinh ra các ước
int a[MAX_N + 5];
int n;

void Input(){
    cin >> n;
    FOR(i, 1, n){
        cin >> a[i];
        pos[a[i]].pb(i); // với mỗi số a[i] thì nó xuất hiện ở những vị trí nào
    }
}

void Sieve_SPF(int limit){ // Tạo mảng spf
    FOR(i, 2, limit) if(!spf[i]){
        spf[i] = i;

        for(ll j = 1LL * i * i; j <= limit; j += i){
            if(!spf[j]) spf[j] = i;
        }
    }
}

void update_best(int d, pii val){ // hàm update cho mảng best
    if(best[d][0] > val){
        best[d][1] = best[d][0];
        best[d][0] = val;
    }
    else if(best[d][1] > val){
        best[d][1] = val;
    }
}

void Prepare(){
    Sieve_SPF(MAX_A);

    omega[1] = 0;
    FOR(i, 2, MAX_A) omega[i] = omega[i / spf[i]] + 1; //tính Ω cho từng số

    FOR(i, 1, MAX_A){
        best[i][0] = best[i][1] = {INF, INF}; // gán trước phòng trước hợp số d không có bội nào tồn tại trong mảng thì kết quả sẽ sau khi dùng công thức sẽ là âm vô cùng -> không ảnh hưởng tới kết quả cuối

        for(int j = i; j <= MAX_A; j += i) if(sz(pos[j])){
                update_best(i, {omega[j], pos[j][0]}); // xem số j có phù hợp để làm số tốt nhất cho best[i] không
                if(sz(pos[j]) > 1) update_best(i, {omega[j], pos[j][1]});// nếu số j xuất hiện 2 lần trong mảng thì cập nhật thêm lần nữa vị biết đâu cả vị trí nhất và nhì thì đều là j nhưng chỉ khác index thì sao

        }
    }
}

vector<int> get_divisors(int x){ // hàm sinh ước
    vector<pii> factor;

    while(x > 1){
        int p = spf[x], cnt = 0;
        while(x % p == 0){
            x /= p;
            cnt++;
        }
        factor.pb({p, cnt});
    }

    vector<int> res = {1};
    for(pii f : factor){
        int p = f.fi, cnt = f.sec;
        int cur = 1, cur_sz = sz(res);

        FOR(i, 1, cnt){
            cur *= p;
            for(int j = 0; j < cur_sz; j++) res.pb(res[j] * cur);
        }
    }

    return res;
}

void update_ans(int &best_idx, int &min_dist, int i, int d, pii good){ //nhìn tự hiểu
    int dist = omega[a[i]] + good.fi - 2 * omega[d];

    if(min_dist > dist){
        min_dist = dist;
        best_idx = good.sec;
    }
    else if(min_dist == dist){
        best_idx = min(best_idx, good.sec);
    }
}

void Solve(){
    FOR(i, 1, n){
        int best_idx, min_dist = INF;

        vector<int> divi = get_divisors(a[i]); // các ước của a[i]
        for(int d : divi){
            if(best[d][0].sec != i) update_ans(best_idx, min_dist, i, d, best[d][0]); // nếu số tốt nhất của d không phải là a[i] thì lấy
            else update_ans(best_idx, min_dist, i, d, best[d][1]); // còn nếu số tốt nhất chính là a[i] thì dùng số tốt nhì
        }

        cout << best_idx << " " << min_dist << el; // cout kết quả
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    Input();
    Prepare();
    Solve();

    return 0;
}