#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 114514
using namespace std;
int head[N],to[N],nxt[N],tot,w[N],e[N],T,n,cnt,mx;
int dfn[N],st[N],top,low[N],co[N],col;
void csh(){
	tot=cnt=top=col=0;
	memset(head,0,sizeof(head));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(co,0,sizeof(co));
}
int add(int u,int v){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
}
void tarjan(int x){
	st[++top]=x;
	dfn[x]=low[x]=++cnt;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]);
		else if(!co[y])low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		co[x]=++col;
		while(st[top]!=x)co[st[top--]]=col;
		top--;
	}
}
signed main(){
	scanf("%d",&T);
	while(T--){
		csh();
		scanf("%d",&n);
		mx=0;
		for(int i=1;i<=n;i++)scanf("%d",&w[i]),mx=max(mx,w[i]);
		for(int i=1;i<=n;i++)scanf("%d",&e[i]),mx=max(mx,w[i]);
		for(int i=1;i<=mx;i++)for(int j=2*i;j<=mx;j+=i)add(i,j);
		for(int i=1;i<=n;i++)add(w[i],e[i]);
		for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
		int ans=0;
		for(int i=1;i<=n;i++)ans+=co[w[i]]==co[e[i]];
		printf("%d\n",ans);
	} 
	return 0;
}