#include <bits/stdc++.h>
using namespace std;
int n, a[500007], d[500007][2];
bool pd[10000007];
int pri[1000007];
void Init() {
  for (int i = 2; i <= 10000000; ++i) {
    if (!pd[i]) {
      pri[++pri[0]] = i;
    }
    for (int j = 1; j <= pri[0] && i * pri[j] <= 10000000; ++j) {
      pd[i * pri[j]] = 1;
      if (i % pri[j] == 0) break;
    }
  }
}
int main() {
  Init();
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i) {
    if (!pd[a[i]]) {
      d[i][0] = d[i][1] = -1;
    } else {
      for (int j = 1; j <= pri[0] && pri[j] <= sqrt(a[i]); ++j)
        if (a[i] % pri[j] == 0) {
          d[i][0] = pri[j];
          while (a[i] % pri[j] == 0) a[i] /= pri[j];
          break;
        }
      if (a[i] != 1)
        d[i][1] = a[i];
      else
        d[i][0] = d[i][1] = -1;
    }
  }
  for (int i = 1; i <= n; ++i) printf("%d ", d[i][0]);
  puts("");
  for (int i = 1; i <= n; ++i) printf("%d ", d[i][1]);
}
