#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
ll modmul(ll a, ll b, ll m){
    return (__int128)a * b % m;
}
 
ll modpow(ll a, ll d, ll m){
    ll r = 1;
    while(d){
        if(d & 1) r = modmul(r, a, m);
        a = modmul(a, a, m);
        d >>= 1;
    }
    return r;
}
 
bool miller(ll n){
    if(n < 2) return false;
    for(ll p : {2,3,5,7,11,13,17,19,23,29,31,37})
        if(n % p == 0) return n == p;
    ll d = n - 1, s = 0;
    while((d & 1) == 0) d >>= 1, s++;
    for(ll a : {2,325,9375,28178,450775,9780504,1795265022}){
        if(a % n == 0) continue;
        ll x = modpow(a, d, n);
        if(x == 1 || x == n - 1) continue;
        bool composite = true;
        for(int r = 1; r < s; r++){
            x = modmul(x, x, n);
            if(x == n - 1){
                composite = false;
                break;
            }
        }
        if(composite) return false;
    }
    return true;
}
 
ll smallest_factor(ll n){
    if(n % 2 == 0) return 2;
    for(ll i = 3; i * i <= n; i += 2)
        if(n % i == 0) return i;
    return n;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    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 = smallest_factor(x);
            ll pw = 1, 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] = v;
            }
        }
 
        for(ll x : b) cout << x << ' ';
        cout << '\n';
        for(ll x : c) cout << x << ' ';
        cout << '\n';
    }
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIGxsID0gbG9uZyBsb25nOwoKbGwgbW9kbXVsKGxsIGEsIGxsIGIsIGxsIG0pewogICAgcmV0dXJuIChfX2ludDEyOClhICogYiAlIG07Cn0KCmxsIG1vZHBvdyhsbCBhLCBsbCBkLCBsbCBtKXsKICAgIGxsIHIgPSAxOwogICAgd2hpbGUoZCl7CiAgICAgICAgaWYoZCAmIDEpIHIgPSBtb2RtdWwociwgYSwgbSk7CiAgICAgICAgYSA9IG1vZG11bChhLCBhLCBtKTsKICAgICAgICBkID4+PSAxOwogICAgfQogICAgcmV0dXJuIHI7Cn0KCmJvb2wgbWlsbGVyKGxsIG4pewogICAgaWYobiA8IDIpIHJldHVybiBmYWxzZTsKICAgIGZvcihsbCBwIDogezIsMyw1LDcsMTEsMTMsMTcsMTksMjMsMjksMzEsMzd9KQogICAgICAgIGlmKG4gJSBwID09IDApIHJldHVybiBuID09IHA7CiAgICBsbCBkID0gbiAtIDEsIHMgPSAwOwogICAgd2hpbGUoKGQgJiAxKSA9PSAwKSBkID4+PSAxLCBzKys7CiAgICBmb3IobGwgYSA6IHsyLDMyNSw5Mzc1LDI4MTc4LDQ1MDc3NSw5NzgwNTA0LDE3OTUyNjUwMjJ9KXsKICAgICAgICBpZihhICUgbiA9PSAwKSBjb250aW51ZTsKICAgICAgICBsbCB4ID0gbW9kcG93KGEsIGQsIG4pOwogICAgICAgIGlmKHggPT0gMSB8fCB4ID09IG4gLSAxKSBjb250aW51ZTsKICAgICAgICBib29sIGNvbXBvc2l0ZSA9IHRydWU7CiAgICAgICAgZm9yKGludCByID0gMTsgciA8IHM7IHIrKyl7CiAgICAgICAgICAgIHggPSBtb2RtdWwoeCwgeCwgbik7CiAgICAgICAgICAgIGlmKHggPT0gbiAtIDEpewogICAgICAgICAgICAgICAgY29tcG9zaXRlID0gZmFsc2U7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBpZihjb21wb3NpdGUpIHJldHVybiBmYWxzZTsKICAgIH0KICAgIHJldHVybiB0cnVlOwp9CgpsbCBzbWFsbGVzdF9mYWN0b3IobGwgbil7CiAgICBpZihuICUgMiA9PSAwKSByZXR1cm4gMjsKICAgIGZvcihsbCBpID0gMzsgaSAqIGkgPD0gbjsgaSArPSAyKQogICAgICAgIGlmKG4gJSBpID09IDApIHJldHVybiBpOwogICAgcmV0dXJuIG47Cn0KCmludCBtYWluKCl7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKG51bGxwdHIpOwoKICAgIGludCB0OwogICAgY2luID4+IHQ7CgogICAgd2hpbGUodC0tKXsKICAgICAgICBpbnQgbjsKICAgICAgICBjaW4gPj4gbjsKCiAgICAgICAgdmVjdG9yPGxsPiBiKG4pLCBjKG4pOwogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspewogICAgICAgICAgICBsbCB4OwogICAgICAgICAgICBjaW4gPj4geDsKCiAgICAgICAgICAgIGxsIHAgPSBzbWFsbGVzdF9mYWN0b3IoeCk7CiAgICAgICAgICAgIGxsIHB3ID0gMSwgdiA9IHg7CgogICAgICAgICAgICB3aGlsZSh2ICUgcCA9PSAwKXsKICAgICAgICAgICAgICAgIHYgLz0gcDsKICAgICAgICAgICAgICAgIHB3ICo9IHA7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGlmKHYgPT0gMSl7CiAgICAgICAgICAgICAgICBiW2ldID0gLTE7CiAgICAgICAgICAgICAgICBjW2ldID0gLTE7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICBiW2ldID0gcHc7CiAgICAgICAgICAgICAgICBjW2ldID0gdjsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgZm9yKGxsIHggOiBiKSBjb3V0IDw8IHggPDwgJyAnOwogICAgICAgIGNvdXQgPDwgJ1xuJzsKICAgICAgICBmb3IobGwgeCA6IGMpIGNvdXQgPDwgeCA8PCAnICc7CiAgICAgICAgY291dCA8PCAnXG4nOwogICAgfQp9Cg==

MTAKMiAzIDQgNSA2IDcgOCA5IDEwIDI0Cg==

10
2 3 4 5 6 7 8 9 10 24