#include <bits/stdc++.h>
using namespace std;
bool notprime[10000010];
int minfac[10000010];
int primes[10000010], cnt = 0;
bool flag[10000010];
void init() {
  notprime[1] = 1;
  for (int i = 2; i <= 10000000; i++) {
    if (notprime[i] == 0) {
      primes[++cnt] = i;
      minfac[i] = i;
    }
    for (int j = 1; j <= cnt; j++) {
      int v = primes[j];
      if (v * i > 10000000) break;
      notprime[v * i] = 1;
      minfac[v * i] = v;
      if (i % v == 0) {
        break;
      }
    }
  }
}
vector<int> as1;
vector<int> as2;
int main() {
  init();
  flag[1] = 1;
  for (long long i = 2; i <= 10000000; i++) {
    if (i * i > 10000000) break;
    if (notprime[i] == 1) continue;
    long long nw = i * i;
    while (nw <= 10000000) {
      flag[nw] = true;
      nw *= i;
    }
  }
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int temp;
    scanf("%d", &temp);
    if (flag[temp] == true || notprime[temp] == 0) {
      as1.push_back(-1);
      as2.push_back(-1);
    } else {
      if (minfac[temp] == 2) {
        int k = temp;
        while (k % 2 == 0) k /= 2;
        as1.push_back(2);
        as2.push_back(k);
      } else {
        as1.push_back(minfac[temp]);
        int k = temp;
        while (k % minfac[temp] == 0) k /= minfac[temp];
        as2.push_back(minfac[k]);
      }
    }
  }
  for (int i = 0; i < as1.size(); i++) {
    if (i) printf(" ");
    printf("%d", as1[i]);
  }
  printf("\n");
  for (int i = 0; i < as2.size(); i++) {
    if (i) printf(" ");
    printf("%d", as2[i]);
  }
  printf("\n");
  return 0;
}
