#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
#define int long long
template<class T>
void read(T &now){
	now=0;
	char c=getchar();
	int f=1;
	while((!isdigit(c))){
		if(c=='-') f=-1;
	//	cout<<isdigit(c)<<" "<<c<<" ";
		c=getchar();
	}
	while(isdigit(c)){
		now=(now<<1)+(now<<3)+c-'0';
		c=getchar();
	}
	now*=f;
}
struct e{
	int to;
	int ne;
	int v;
}ed[7000000];
int le[7000001];
int head[7000001];
int ppp=1;
int fr[7000001];
int n,m;
int b[7000001];
int r[7000001];
int prime[7000001];
int cnt;
int p;
queue<int> q;
int vis[7000001];
void add(int f,int to,int v){
	ed[++ppp].to=to;ed[ppp].ne=head[f];head[f]=ppp;ed[ppp].v=v;
	ed[++ppp].to=f;ed[ppp].ne=head[to];head[to]=ppp;ed[ppp].v=0;
}
void pri(){
	for(int i=2;i<=10000;++i){
		if(!vis[i]){
			prime[++p]=i;
			vis[i]=1;
		}
		for(int j=1;j<=p&&prime[j]*i<=10000;++j){
			vis[prime[j]*i]=1;
			if(i%prime[j]==0) break;
		}
	}
}
int inf=(1<<20);
int x;
void wb(int x,int i){
	for(int j=1;j<=p;++j){
		if(prime[j]>x) return ;
		if(x%prime[j]==0){
			add(p+i,j,inf);
		}
		
	}
}
void wr(int x,int i){
	for(int j=1;j<=p;++j){
		if(prime[j]>x) return ;
		if(x%prime[j]==0){
			add(j,p+m+i,inf);
		}
		
	}
}
int s,t;
bool bfs(){
	while(!q.empty()) q.pop();
	q.push(s);
	memset(le,-1,sizeof(le));
	le[s]=0;
//vis[s]=1;
	fr[s]=head[s];
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=ed[i].ne){
			int v=ed[i].to;
			if(le[v]==-1&&ed[i].v){
				le[v]=le[x]+1;
				fr[v]=head[v];
				q.push(v);
				if(v==t) return 1;
			}
		}
	}
	return 0;
}
int dfs(int no,int tas){
	if(no==t){
		return tas;
	}
	int res=0;
	for(int i=fr[no];i;i=ed[i].ne){
		int v=ed[i].to;
		fr[no]=i;
		if(ed[i].v==0||le[v]!=le[no]+1) continue;
		int get=dfs(v,min(tas-res,ed[i].v));
		if(get==0) le[v]=-1;
		ed[i].v-=get;;
		ed[i^1].v+=get;;
		res+=get; 
	}
	return res;;
}
int dinic(){
	int ans=0;
	int tem=0;
	while(bfs()){
		while(tem=dfs(s,inf))
			ans+=tem;
	}
	return ans;
}
int T;
signed main(){
	pri();
	read(T);;
	while(T--){
	memset(head,0,sizeof(head));
	ppp=0;
	read(m);read(n);
	for(int i=1;i<=m;++i){
		read(x);
		wb(x,i);
	}
	for(int i=1;i<=n;++i){
		read(x);
		wr(x,i);
	}
	for(int i=1;i<=m;++i){
		add(p+m+n+1,i+p,1);
	}
	s=p+m+n+1;
	t=p+m+n+2;
	for(int i=1;i<=n;++i){
		add(i+p+m,p+m+n+2,1);
	}
	cout<<dinic()<<endl;;
	}
	return 0;
}