#include <bits/stdc++.h>
using namespace std;
int _toggle(int N, int pos) { return N = N ^ (1 << pos); }
int _set(int N, int pos) { return N = N | (1 << pos); }
int _reset(int N, int pos) { return N = N & ~(1 << pos); }
bool _check(int N, int pos) { return (bool)(N & (1 << pos)); }
bool _upper(char a) { return a >= 'A' && a <= 'Z'; }
bool _lower(char a) { return a >= 'a' && a <= 'z'; }
bool _digit(char a) { return a >= '0' && a <= '9'; }
int dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, 1, -1, -1, 1, -1, 1};
bool prime[10000005];
vector<int> P;
void sv() {
  int n = 1e7 + 1;
  for (int i = 2; i * i <= n; i++) {
    if (!prime[i]) {
      P.push_back(i);
      for (int j = i * i; j <= n; j += i) {
        prime[j] = 1;
      }
    }
  }
}
int n, a[500005], b[500005], x, y;
void out(int A) {
  x = -1, y = -1;
  for (auto i : P) {
    if (i > A) {
      break;
    }
    if (A % i) {
      continue;
    }
    while (A % i == 0) {
      A /= i;
    }
    if (A > 1) {
      x = A, y = i;
      return;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  sv();
  for (int i = 1; i <= n; i++) {
    int A;
    cin >> A;
    out(A);
    a[i] = x, b[i] = y;
  }
  for (int i = 1; i <= n; i++) {
    cout << a[i] << ' ';
  }
  cout << '\n';
  for (int i = 1; i <= n; i++) {
    cout << b[i] << ' ';
  }
}
