#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int MAXN = 10000000;
vector<int> spf(MAXN + 1);
 
void sieve() {
    for(int i = 2; i <= MAXN; i++) {
        if(spf[i] == 0) {
            for(int j = i; j <= MAXN; j += i) {
                if(spf[j] == 0) spf[j] = i;
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    sieve();
 
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
 
        vector<ll> b(n), c(n);
        for(int i = 0; i < n; i++) {
            ll x;
            cin >> x;
 
            ll p = spf[x];
            if(p == 0) {
                b[i] = -1;
                c[i] = -1;
                continue;
            }
 
            ll pw = 1;
            ll v = x;
            while(v % p == 0) {
                v /= p;
                pw *= p;
            }
 
            if(v == 1) {
                b[i] = -1;
                c[i] = -1;
            } else {
                b[i] = pw;
                c[i] = x / pw;
            }
        }
 
        for(int i = 0; i < n; i++) cout << b[i] << ' ';
        cout << '\n';
        for(int i = 0; i < n; i++) cout << c[i] << ' ';
        cout << '\n';
    }
 
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIGxsID0gbG9uZyBsb25nOwoKY29uc3QgaW50IE1BWE4gPSAxMDAwMDAwMDsKdmVjdG9yPGludD4gc3BmKE1BWE4gKyAxKTsKCnZvaWQgc2lldmUoKSB7CiAgICBmb3IoaW50IGkgPSAyOyBpIDw9IE1BWE47IGkrKykgewogICAgICAgIGlmKHNwZltpXSA9PSAwKSB7CiAgICAgICAgICAgIGZvcihpbnQgaiA9IGk7IGogPD0gTUFYTjsgaiArPSBpKSB7CiAgICAgICAgICAgICAgICBpZihzcGZbal0gPT0gMCkgc3BmW2pdID0gaTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQoKaW50IG1haW4oKSB7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKG51bGxwdHIpOwoKICAgIHNpZXZlKCk7CgogICAgaW50IHQ7CiAgICBjaW4gPj4gdDsKICAgIHdoaWxlKHQtLSkgewogICAgICAgIGludCBuOwogICAgICAgIGNpbiA+PiBuOwoKICAgICAgICB2ZWN0b3I8bGw+IGIobiksIGMobik7CiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgICAgICBsbCB4OwogICAgICAgICAgICBjaW4gPj4geDsKCiAgICAgICAgICAgIGxsIHAgPSBzcGZbeF07CiAgICAgICAgICAgIGlmKHAgPT0gMCkgewogICAgICAgICAgICAgICAgYltpXSA9IC0xOwogICAgICAgICAgICAgICAgY1tpXSA9IC0xOwogICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGxsIHB3ID0gMTsKICAgICAgICAgICAgbGwgdiA9IHg7CiAgICAgICAgICAgIHdoaWxlKHYgJSBwID09IDApIHsKICAgICAgICAgICAgICAgIHYgLz0gcDsKICAgICAgICAgICAgICAgIHB3ICo9IHA7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGlmKHYgPT0gMSkgewogICAgICAgICAgICAgICAgYltpXSA9IC0xOwogICAgICAgICAgICAgICAgY1tpXSA9IC0xOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgYltpXSA9IHB3OwogICAgICAgICAgICAgICAgY1tpXSA9IHggLyBwdzsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykgY291dCA8PCBiW2ldIDw8ICcgJzsKICAgICAgICBjb3V0IDw8ICdcbic7CiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykgY291dCA8PCBjW2ldIDw8ICcgJzsKICAgICAgICBjb3V0IDw8ICdcbic7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K

MTAKMiAzIDQgNSA2IDcgOCA5IDEwIDI0Cg==

10
2 3 4 5 6 7 8 9 10 24