#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=5e2+10,INF=1e8;

int tt,n,m,b[N],r[N],cnt,ans,to[N*N],net[N*N],hea[N],s,t;
int q[N],hh,ww,dep[N],yu[N];

int read() {
	char ch;
	int x=0;
	ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') {
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	} 
	return x;
}

void init() {
	cnt=1;
	ans=0;
	s=0;t=n+m+1;
}

void add(int x,int y,int z) {
	to[++cnt]=y;
	yu[cnt]=z;
	net[cnt]=hea[x];
	hea[x]=cnt;
}

bool ff(){
    queue<int> q;
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=hea[x];i;i=net[i]){
            int y=to[i];
            if(yu[i]&&!dep[y]){
                dep[y]=dep[x]+1;
                q.push(y);
            }
        }
    }
    return dep[t];
}

int dfs(int u,int in){
    if(u==t) return in;
    int out=0;
    for(int i=hea[u];i&&in;i=net[i]){
        int v=to[i];
        if(yu[i]&&dep[v]==dep[u]+1){
            int res=dfs(v,min(in,yu[i]));
            yu[i]-=res;
            yu[i^1]+=res;
            in-=res;
            out+=res;
        }
    }
    if(out==0) dep[u]=0;
    return out;
}

int main() {
	
	tt=read();
	while(tt--) {
		m=read();n=read();
		for(int i=1;i<=m;i++) b[i]=read();
		for(int i=1;i<=n;i++) r[i]=read();
		init();
		for(int i=1;i<=m;i++) {
			add(0,i,INF);
			add(i,0,0);
		}
		for(int i=m+1;i<=n+m;i++) {
			add(i,n+m+1,INF);
			add(n+m+1,i,0);
		}
		for(int i=1;i<=m;i++) {
			for(int j=1;j<=n;j++) {
				int gg;
				gg=__gcd(b[i],r[j]);
				if(gg>1) {
					add(i,j+m,1);
					add(j+m,i,0);
				}
			}
		}
		while(ff()) ans+=dfs(s,INF);
		printf("%d\n",ans);
	}
	
	return 0;
}