rt

#include<bits/stdc++.h>
#define ORZ cerr<<"sto apple365 orz\n"
using namespace std;
const int N=2e4+5,M=1e6+5,inf=0x3f3f3f3f;
int n,m,s,t;
int a[N],b[N];
int now[N],head[N],tot;
struct{int to,flow,cap,nxt;}edge[M];
void addedge(int u,int v,int cap)
{
    ++tot;
    edge[tot].to=v;
    edge[tot].flow=0;
    edge[tot].cap=cap;
    edge[tot].nxt=head[u];
    head[u]=tot;
    ++tot;
    edge[tot].to=u;
    edge[tot].flow=0;
    edge[tot].cap=0;
    edge[tot].nxt=head[v];
    head[v]=tot;
}
int prime[N],k;
bool np[N];
void init()
{
    for(int i=2;i<N;++i)
    {
        if(!np[i])
            prime[++k]=i;
        for(int j=1;j<=k&&i*prime[j]<N;++j)
        {
            np[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int dep[M];
bool bfs()
{
	memset(dep,0,sizeof dep);
	queue<int>q;
	q.emplace(s);
	dep[s]=1;
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int v=edge[i].to;
			if(edge[i].flow<edge[i].cap&&!dep[v])
				q.emplace(v),dep[v]=dep[u]+1;
		}
	}
	return (dep[t]>0);
}
int dfs(int u,int f)
{
	if(u==t||!f)
		return f;
	int res=0;
	for(int &i=now[u];i;i=edge[i].nxt)
	{
		int v=edge[i].to,d=0;
		if(dep[u]+1==dep[v]&&(d=dfs(v,min(f-res,edge[i].cap-edge[i].flow))))
		{
			res+=d;
			edge[i].flow+=d;
			edge[i^1].flow-=d;
			if(res==f)
				return res;
		}
	}
	return res;
}
int dinic()
{
    int res=0;
    while(bfs())
    {
        // ORZ;
        for(int i=1;i<=t;i++)
            now[i]=head[i];
        res+=dfs(s,inf);
    }
    return res;
}
void solve()
{
    memset(head,0,sizeof head);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=m;++i)
        cin>>b[i];
    s=n+m+k+1;t=s+1;
    for(int i=1;i<=n;++i)
        addedge(s,i,1);
    for(int i=1;i<=m;++i)
        addedge(i+n,t,1);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=k;++j)
            if(a[i]%prime[j]==0)
                addedge(i,n+m+j,1);
    for(int i=1;i<=m;++i)
        for(int j=1;j<=k;++j)
            if(b[i]%prime[j]==0)
                addedge(n+m+j,i+n,1);
    cout<<dinic()<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    int T;
    for(cin>>T;T;--T)
        solve();
    // cout<<".";
}