#include <bits/stdc++.h>
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
using namespace std;
class Sieve {
 private:
  ::std::vector<bool> prime;

 public:
  Sieve(int n) : prime(n + 1, true) {
    prime[0] = prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
      if (!prime[i]) continue;
      for (int j = i * 2; j <= n; j += i) {
        prime[j] = false;
      }
    }
  }
  bool isprime(int x) { return prime[x]; }
};
int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  Sieve sieve((long long)1e7);
  vector<long long> prime;
  for (int i = 0; i < (int)((long long)1e7 + 1); i++)
    if (sieve.isprime(i)) prime.push_back(i);
  vector<pair<int, int> > ans(N, pair<int, int>(-1, -1));
  for (int i = 0; i < (int)(N); i++) {
    long long a;
    cin >> a;
    for (int j = 0; prime[j] * prime[j] <= a; j++) {
      if (a % prime[j] == 0) {
        long long m = 1;
        while (a % prime[j] == 0) {
          a /= prime[j];
          m *= prime[j];
        }
        if (a > 1 && m > 1) {
          ans[i].first = a;
          ans[i].second = m;
        }
        break;
      }
    }
  }
  for (int i = 0; i < (int)(N); i++) {
    if (i > 0) cout << " ";
    cout << ans[i].first;
  }
  cout << "\n";
  for (int i = 0; i < (int)(N); i++) {
    if (i > 0) cout << " ";
    cout << ans[i].second;
  }
  cout << "\n";
  return 0;
}
