#include <bits/stdc++.h>
using namespace std;
int n, prime[10000010];
set<int> del;
vector<pair<int, int> > ans;
void init() {
  for (long long i = 2; i <= 10000000; i++) {
    if (!prime[i]) {
      prime[i] = i;
      for (long long j = i * i; j <= 10000000; j += i) prime[j] = i;
    }
  }
}
int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  init();
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    del.clear();
    while (prime[x]) {
      del.insert(prime[x]);
      x /= prime[x];
    }
    int p = 1, l = del.size();
    if (l == 1) {
      ans.push_back({-1, -1});
      continue;
    }
    for (auto u : del) p *= u;
    int t = *del.begin();
    ans.push_back({t, p / t});
  }
  for (auto u : ans) cout << u.first << ' ';
  cout << '\n';
  for (auto u : ans) cout << u.second << ' ';
  cout << '\n';
  return 0;
}
