#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 7;
const int MAXN = 1e7 + 5;
int t;
int n, m;
vector<int> pf;
vector<int> prime;
bitset<MAXN> vis;
int b[maxn], c[maxn];
void init() {
  pf.resize(MAXN, 0);
  vis.flip();
  vis[0] = vis[1] = false;
  for (int i = 2; i < MAXN; i++) {
    if (vis[i]) {
      prime.push_back(i);
      pf[i] = i;
    }
    for (auto x : prime) {
      if (1LL * i * x >= MAXN) break;
      pf[i * x] = x;
      vis[i * x] = false;
      if (i % x == 0) break;
    }
  }
}
int main() {
  while (cin >> n) {
    memset(b, -1, sizeof(b));
    memset(c, -1, sizeof(c));
    init();
    for (int i = 0; i < n; i++) {
      int x;
      cin >> x;
      int k1 = x, k2 = 1;
      while (k1 % pf[x] == 0) {
        k1 /= pf[x];
        k2 *= pf[x];
      }
      if (k1 > 1) {
        b[i] = k1, c[i] = k2;
      }
    }
    for (int i = 0; i < n; i++) cout << b[i] << " ";
    cout << endl;
    for (int i = 0; i < n; i++) cout << c[i] << " ";
    cout << endl;
  }
}
