#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int MAXN = 10000000;
vector<int> spf(MAXN + 1, 0);
 
void sieve(){
    for(int i = 2; i <= MAXN; i++){
        if(!spf[i]){
            for(int j = i; j <= MAXN; j += i){
                if(!spf[j]) spf[j] = i;
            }
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    sieve();
 
    int t = 1;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
 
        vector<ll> b(n, -1), c(n, -1);
        for(int i = 0; i < n; i++){
            ll x;
            cin >> x;
 
            ll v = x;
            ll p = spf[v];
            if(p == 0){
                b[i] = -1;
                c[i] = -1;
                continue;
            }
 
            ll pw = 1;
            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+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIGxsID0gbG9uZyBsb25nOwoKY29uc3QgaW50IE1BWE4gPSAxMDAwMDAwMDsKdmVjdG9yPGludD4gc3BmKE1BWE4gKyAxLCAwKTsKCnZvaWQgc2lldmUoKXsKICAgIGZvcihpbnQgaSA9IDI7IGkgPD0gTUFYTjsgaSsrKXsKICAgICAgICBpZighc3BmW2ldKXsKICAgICAgICAgICAgZm9yKGludCBqID0gaTsgaiA8PSBNQVhOOyBqICs9IGkpewogICAgICAgICAgICAgICAgaWYoIXNwZltqXSkgc3BmW2pdID0gaTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQoKaW50IG1haW4oKXsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUobnVsbHB0cik7CgogICAgc2lldmUoKTsKCiAgICBpbnQgdCA9IDE7CiAgICBjaW4gPj4gdDsKICAgIHdoaWxlKHQtLSl7CiAgICAgICAgaW50IG47CiAgICAgICAgY2luID4+IG47CgogICAgICAgIHZlY3RvcjxsbD4gYihuLCAtMSksIGMobiwgLTEpOwogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspewogICAgICAgICAgICBsbCB4OwogICAgICAgICAgICBjaW4gPj4geDsKCiAgICAgICAgICAgIGxsIHYgPSB4OwogICAgICAgICAgICBsbCBwID0gc3BmW3ZdOwogICAgICAgICAgICBpZihwID09IDApewogICAgICAgICAgICAgICAgYltpXSA9IC0xOwogICAgICAgICAgICAgICAgY1tpXSA9IC0xOwogICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGxsIHB3ID0gMTsKICAgICAgICAgICAgd2hpbGUodiAlIHAgPT0gMCl7CiAgICAgICAgICAgICAgICB2IC89IHA7CiAgICAgICAgICAgICAgICBwdyAqPSBwOwogICAgICAgICAgICB9CgogICAgICAgICAgICBpZih2ID09IDEpewogICAgICAgICAgICAgICAgYltpXSA9IC0xOwogICAgICAgICAgICAgICAgY1tpXSA9IC0xOwogICAgICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgICAgIGJbaV0gPSBwdzsKICAgICAgICAgICAgICAgIGNbaV0gPSB4IC8gcHc7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspIGNvdXQgPDwgYltpXSA8PCAnICc7CiAgICAgICAgY291dCA8PCAnXG4nOwogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspIGNvdXQgPDwgY1tpXSA8PCAnICc7CiAgICAgICAgY291dCA8PCAnXG4nOwogICAgfQoKICAgIHJldHVybiAwOwp9Cg==

MTAKMiAzIDQgNSA2IDcgOCA5IDEwIDI0Cg==

10
2 3 4 5 6 7 8 9 10 24