#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define b first
#define d second
#define sd(n) scanf("%d",&n)
#define SIZE(A) ((int)(A).size())
#define PB push_back
#define MP make_pair
vector < int >  ed1,ed2;
typedef long long llint;
typedef pair<int, int> edge;
typedef edge par;

const int MAX = 300005;
const int inf = 2000000000;

class Dinic {
    vector< edge > E[MAX];
    vector< int > cap[MAX];
    int dist[MAX];
    int bio[MAX];
    int sh[MAX];
    int cookie, s, t;

    queue<int> Q;
    int bfs() {
        cookie++;
        while(!Q.empty()) Q.pop();

        bio[s] = cookie;
        dist[s] = 0;
        Q.push(s);
        while(!Q.empty()) {
            int x = Q.front();
            Q.pop();

            for(int i = 0; i < (int)E[x].size(); ++i) {
                int y = E[x][i].b;
                if((bio[y] != cookie || y == t) && cap[x][i] != 0) {
                    dist[y] = dist[x]+1;
                    bio[y] = cookie;
                    if(y != t) Q.push(y);
                }
            }
        }
        return bio[t] == cookie;
    }

    int augment(int x, int c) {
        if(x == t) return c;

        for(int i = sh[x]; i < (int)E[x].size(); ++i, ++sh[x]) {
            int y = E[x][i].b;
            if(cap[x][i] > 0 && bio[y] == cookie && ( y == t || dist[y] == dist[x]+1)) {
                int v = augment(y, c = min(c, cap[x][i]));
                if(v > 0) { cap[x][i] -= v, cap[y][E[x][i].d] += v; return v; }
            }
        }
        return 0;
    }

    public:
    void doso()
    {
        for(int i=0; i<MAX; i++)
            E[i].clear(),cap[i].clear();
        cookie=s=t=0;
        while(!Q.empty()) Q.pop();
        memset(dist,0,sizeof(dist));
        memset(bio,0,sizeof(bio));
        memset(sh,0,sizeof(sh));
    }
    public:
    void add_edge(int a, int b, int cab, int cba) {
        E[a].push_back(edge(b, E[b].size()));
        E[b].push_back(edge(a, E[a].size()-1));
        cap[a].push_back(cab);
        cap[b].push_back(cba);
    }

    int maxflow(int S, int T) {
        s = S, t = T;
        llint ans = 0;
        while(bfs()) {
            int f;
            memset(sh, 0, (T+1)*4);
            while((f = augment(s, inf))) ans += f;
        }
        return ans;
    }
} D;

const int MAXN = 106105;

int a[MAXN];
int b[MAXN];
par A[MAXN], B[MAXN];

vector<int> va[MAXN], vb[MAXN];
map<int, int> M, I;

int v1[1000005], v2[1000005], v[1000005];
int p1, p2, p;

int ima(int x) {
    int lo = 0, hi = p-1;
    while(lo < hi) {
        int mid = (lo + hi)/2;
        if(v[mid] < x) lo = mid+1; else
            hi = mid;
    }
    return v[lo] == x ? lo : -1;
}

int pr[10000], prn;

int solve()
{
    M.clear();
    I.clear();
    prn=0,p1=0,p2=0,p=0;
    for(int i = 2; i < 33000; ++i) {
        bool ok = true;
        for(int j = 2; j*j <= i; ++j)
            if(i%j == 0) { ok = false; break; }
        if(ok) pr[prn++] = i;
    }

    int n;
    n=ed1.size();
    for(int i=0; i<MAXN; i++)
        va[i].clear(),vb[i].clear();
    for(int i = 0; i < n; ++i)
        a[i]=ed1[i];
    for(int i = 0; i < n; ++i)
        b[i]=ed2[i];
    for(int i = 0; i < n; ++i) {
        int x = a[i], y = b[i];
        if(x>1)
        {
            for(int j = 0; j < prn && pr[j]*pr[j] <= x; ++j)
                if(x%pr[j] == 0) {
                    x /= pr[j];
                    va[i].push_back(pr[j]);
                    v1[p1++] = pr[j];
                    while(x%pr[j] == 0) x /= pr[j];
                }
            if(x > 1) v1[p1++] = x, va[i].push_back(x);
        }
        if(y>1)
        {
            for(int j = 0; j < prn && pr[j]*pr[j] <= y; ++j)
                if(y%pr[j] == 0) {
                    y /= pr[j];
                    v2[p2++] = pr[j];
                    vb[i].push_back(pr[j]);
                    while(y%pr[j] == 0) y /= pr[j];
                }
            if(y > 1) v2[p2++] = y, vb[i].push_back(y);
        }
    }

    sort(v1, v1+p1);
    sort(v2, v2+p2);

    p1 = (unique(v1, v1+p1) - v1);
    p2 = (unique(v2, v2+p2) - v2);

    int pt = 0;
    for(int i = 0; i < p1; ++i) {
        while(pt < p2 && v2[pt] < v1[i]) pt++;
        if(pt < p2 && v1[i] == v2[pt]) v[p++] = v1[i];
    }

    int S = MAX-2, T = S+1;
    int N = 0, N2 = 0;
    for(int i = 0; i < n; ++i) {
        int y = 1;
        for(int j = 0; j < (int)va[i].size(); ++j)
            if(ima(va[i][j]) != -1) y *= va[i][j];

        if(M.count(y) == false) {
            M[y] = 0;
            for(int j = 0; j < (int)va[i].size(); ++j) {
                int q = ima(va[i][j]);
                if(q != -1) D.add_edge(N, MAX-2-q-1, inf, 0);
            }
            I[y] = N++;
        }
        M[y]++;
    }

    for(map<int, int> :: iterator it = M.begin(); it != M.end(); ++it)
        D.add_edge(S, I[it->first], it->second, 0);
    M.clear(), I.clear();
    for(int i = 0; i < n; ++i) {
        int y = 1;
        for(int j = 0; j < (int)vb[i].size(); ++j)
            if(ima(vb[i][j]) != -1) y *= vb[i][j];

        if(M.count(y) == false) {
            M[y] = 0;
            for(int j = 0; j < (int)vb[i].size(); ++j) {
                int q = ima(vb[i][j]);
                if(q != -1) D.add_edge(MAX-2-q-1, N+N2, inf, 0);
            }  
            I[y] = N2++;
        }
        M[y]++;
    }

    for(map<int, int> :: iterator it = M.begin(); it != M.end(); ++it)
        D.add_edge(N+I[it->first], T, it->second, 0);
    return D.maxflow(S, T);
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        ed1.clear();ed2.clear();
        int n,i,j,ans,ar[5000],arr[5000];
        sd(n);
        for(i=0; i<n; i++)
            sd(ar[i]);
        for(i=0;i<n; i++)
            sd(arr[i]);
        sort(ar,ar+n);
        sort(arr,arr+n);
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
                if(arr[j]>ar[i] && __gcd(arr[j],ar[i])!=1)
                    ed1.pb((__gcd(arr[j],ar[i])));
        }
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
                if(ar[j]>arr[i] && __gcd(ar[j],arr[i])!=1)
                    ed2.pb(__gcd(ar[j],arr[i]));
        }
        while(ed1.size()<ed2.size())ed1.pb(1);
        while(ed2.size()<ed1.size())ed2.pb(1);
        D.doso();
        cout << solve()  << endl;
    }
    return 0;
}