//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
 
ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}
 
ll gcd(ll a, ll b){
    if(b == 0)  return a;
    return gcd(b, a%b);
}


int sieve[1000*1000+2], last[2][1000*1000+2];
ll reduced_form[1000*1000+2], complement[1000*1000+2];
ll cnt[2][1000*1000+2];
set<int> distinct;


int main(){

    ios_base::sync_with_stdio(0);

    for(int i=1;i<=1000*1000;i++)
        reduced_form[i] = complement[i] = 1;

    sieve[1] = 1;
    int x = 1000*1000;
    for(int i=2;i<=x;i++)
        if(!sieve[i]){
            for(int j=i;j<=x;j+=i){
                sieve[j] = 1;
                int cnt = 0, val = j;
                while(val % i == 0){
                    val /= i;
                    cnt++;
                }
                cnt %= 3;
        // if(j == 6)  cout<<"got "<<cnt<<" for i = "<<i<<endl;
                if(cnt != 0){
                    // reduced_form[j].pb({i, cnt});
                    // complement[j].pb({i, 3-cnt});
                    reduced_form[j] *= pwr(i, cnt, (ll)1e15);
                    complement[j] *= pwr(i, 3-cnt, (ll)1e15);
                }
            }
        }

// cout<<"reduced_form: ";for(int i=1;i<=20;i++)   cout<<i<<":"<<reduced_form[i]<<" ";cout<<endl;
// cout<<"complement: ";for(int i=1;i<=20;i++)   cout<<i<<":"<<complement[i]<<" ";cout<<endl;

    int T;
    cin>>T;
    // T=1;
    for(int t=1;t<=T;t++){

        distinct.clear();
       
        int n1, n2;
        cin>>n1>>n2;

        while(n1--){
            int a;
            cin>>a;
            int r = reduced_form[a];
            if(last[0][r] != t){
                last[0][r] = t;
                cnt[0][r] = 0;
            }
            cnt[0][r]++;
            distinct.insert(r);
        }

        while(n2--){
            int a;
            cin>>a;
            int r = reduced_form[a];
            if(last[1][r] != t){
                last[1][r] = t;
                cnt[1][r] = 0;
            }
            cnt[1][r]++;
            distinct.insert(r);
        }


// cout<<"distinct: ";for(auto it : distinct)  cout<<it<<" ";cout<<endl;

        ll ans = -1;
        for(auto it : distinct){

            if(last[0][it]==t && complement[it]<=1000*1000 && last[1][complement[it]]==t)
                ans = max(ans, cnt[0][it]*cnt[0][it] + cnt[1][complement[it]]*cnt[1][complement[it]]);

            if(last[1][it]==t && complement[it]<=1000*1000 && last[0][complement[it]]==t)
                ans = max(ans, cnt[1][it]*cnt[1][it] + cnt[0][complement[it]]*cnt[0][complement[it]]);
        }

        cout<<ans<<endl;
    }

    return 0;
}