#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N = 1000 + 10;
const int MAXN = 10000000 + 10;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int check[MAXN];
int num[MAXN];
int prime[MAXN] = {0};
int v[MAXN];
int a[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int i = 1; i <= 10000000; i++) num[i] = i;
  int pos = 0;
  for (int i = 2; i <= 10000000; i++) {
    if (!check[i]) {
      prime[pos++] = i;
    }
    for (int j = 0; j < pos && i * prime[j] <= 10000000; j++) {
      check[i * prime[j]] = 1;
      if (num[i * prime[j]] % prime[j] == 0 && v[i * prime[j]] == 0) {
        v[i * prime[j]] = prime[j];
        while (num[i * prime[j]] % prime[j] == 0) {
          num[i * prime[j]] /= prime[j];
        }
      }
      if (i % prime[j] == 0) {
        break;
      }
    }
  }
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++)
    if (check[a[i]] && num[a[i]] != 1 && v[a[i]])
      cout << v[a[i]] << " ";
    else
      cout << -1 << " ";
  cout << endl;
  for (int i = 1; i <= n; i++)
    if (check[a[i]] && num[a[i]] != 1 && v[a[i]])
      cout << num[a[i]] << " ";
    else
      cout << -1 << " ";
  cout << endl;
  return 0;
}
