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

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

    int n;
    cin >> n;
    vector<int> a(n), d1(n, -1), d2(n, -1);

    for (int i = 0; i < n; ++i) cin >> a[i];

    for (int i = 0; i < n; ++i) {
        int x = a[i];
        vector<int> divisors;

        for (int d = 2; d * d <= x; ++d) {
            if (x % d == 0) {
                divisors.push_back(d);
                if (d != x / d) divisors.push_back(x / d);
            }
        }

        int found = 0;
        for (int j = 0; j < (int)divisors.size(); ++j) {
            for (int k = j + 1; k < (int)divisors.size(); ++k) {
                int p = divisors[j], q = divisors[k];
                if (__gcd(p + q, x) == 1) {
                    d1[i] = p;
                    d2[i] = q;
                    found = 1;
                    break;
                }
            }
            if (found) break;
        }
    }

    for (int x : d1) cout << x << ' ';
    cout << '\n';
    for (int x : d2) cout << x << ' ';
    cout << '\n';

    return 0;
}