#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)

using ll = long long;

template<typename X, typename Y>
bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
template<typename X, typename Y>
bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }


const int INF = 1e9 + 67;
const int MAXA = 1e6;
const int MAXN = 1e5 + 5;

int N, A[MAXN];

namespace Subtask1 {
    bool check() {
        return N == 2;
    }
    int cnt[MAXA + 5];
    void solve() {
        int T = A[1];
        FOR(p, 2, (int)sqrt(T)) if (T % p == 0) {
            int e = 0;
            while (T % p == 0) T /= p, e++;
            cnt[p] = e;
        }
        if (T > 1) cnt[T] = 1;
        T = A[2];
        int D = 0;
        FOR(p, 2, MAXA) {
            if (T % p == 0) {
                int e = 0;
                while (T % p == 0) T /= p, e++;
                D += abs(e - cnt[p]);
            } else D += cnt[p];
        }
        cout << D << " " << 2 << "\n";
        cout << D << " " << 1 << "\n";
    }
}

int spf[MAXA];

void precompute() {
    FOR(i, 1, MAXA) spf[i] = i;
    for (int i = 2; i * i <= MAXA; i++) if (spf[i] == i)
        for (int j = i * i; j <= MAXA; j += i) if (spf[j] == j) 
            spf[j] = i;
}

namespace Subtask2 {
    bool check() {
        return N <= 1000;
    }
    int F[MAXA + 5];
    int f(int x, int y) { return F[x] + F[y] - 2 * F[__gcd(x, y)]; }
    void solve() {
        precompute();
        FOR(i, 2, MAXA) F[i] = F[i / spf[i]] + 1;
        vector<pair<int, int>> ans(N + 5, make_pair(INF, -1));
        FOR(i, 1, N) FOR(j, i + 1, N) {
            int D = f(A[i], A[j]);
            chmin(ans[i], make_pair(D, j));
            chmin(ans[j], make_pair(D, i));
        }
        FOR(i, 1, N) cout << ans[i].first << " " << ans[i].second << "\n";
    }
}

namespace Fulltask {
    vector<int> primes;
    pair<int, int> best[MAXA + 5], _best[MAXA + 5];
    inline bool update(int u, int d, int id) {
        if (id == -1) return false;
        pair<int, int> X = make_pair(d, id);
        if (id == best[u].second) return chmin(best[u], X);
        if (id == _best[u].second) return chmin(_best[u], X);
        if (X < best[u]) {
            _best[u] = best[u];
            best[u] = X;
            return true;
        }
        return chmin(_best[u], X);
    }
    inline void merge(int v, int u) {
        if (best[u].second != -1) update(v, best[u].first + 1, best[u].second);
        if (_best[u].second != -1) update(v, _best[u].first + 1, _best[u].second);
    }
    void solve() {
        precompute();
        FOR(i, 2, MAXA) if (spf[i] == i) 
            primes.push_back(i);
        FOR(i, 1, MAXA) best[i] = _best[i] = make_pair(INF, -1);
        FOR(i, 1, N) update(A[i], 0, i);
        FORD(u, MAXA, 2) if (best[u].second != -1) {    
            int T = u;
            while (T > 1) {
                int p = spf[T];
                merge(u / p, u);
                while (T % p == 0) T /= p;
            }
        }
        FOR(u, 1, MAXA) if (best[u].second != -1) {
            for (int p : primes) {
                if (1LL * u * p > MAXA) break;
                merge(u * p, u);
            }
        }
        FOR(i, 1, N) {
            pair<int, int> ans = make_pair(INF, -1);
            if (best[A[i]].second != -1 && best[A[i]].second != i) chmin(ans, best[A[i]]);
            if (_best[A[i]].second != -1 && _best[A[i]].second != i) chmin(ans, _best[A[i]]);
            cout << ans.first << " " << ans.second << "\n";
        }
    }
}

void solve() {
    cin >> N;
    FOR(i, 1, N) cin >> A[i];
    if (Subtask1::check()) Subtask1::solve();
    else if (Subtask2::check()) Subtask2::solve();
    else Fulltask::solve();
}

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

    // freopen("ENERGY.INP", "r", stdin);
    // freopen("ENERGY.OUT", "w", stdout);

    int tests = 1; // cin >> tests;
    while (tests--) solve();

    #ifdef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
    return 0;
}