inline void prework()
{
	for(int i=2;i<=1e5;i++)
	{
		if(!flag[i]) prime[++len]=i;
		for(int j=1;j<=len && prime[j]*i<=1e5;j++)
		{
			flag[prime[j]*i]=true;
			if(i%prime[j]==0) break;
		}
	}
//	for(int i=1;i<=20;i++) cout<<prime[i]<<" ";
//	cout<<endl;
	for(int i=1;i<=1e5;i++)
		for(int j=1;j<=len && i*prime[j]<=1e5;j++)
			add(i,i*prime[j]);
	cur_s=s; 
	for(int i=1;i<=1e5;i++) 
		cur[i]=head[i];
}

inline void build_edge()
{
	s=cur_s; for(int i=1;i<=1e5;i++) head[i]=cur[i];
	for(int i=1;i<=n;i++) add(a[i],c[i]);
}

int main()
{	
	prework();
	int Q=read();
	while(Q--)
	{
		n=read();
		for(int i=1;i<=n;i++) a[i]=read();
		for(int i=1;i<=n;i++) c[i]=read();
		build_edge();
		memset(dfn,0,sizeof(dfn));
		cnt=top=tot=0;
		for(int i=1;i<=1e5;i++)
			if(!dfn[i])
				tarjan(i);	
		int ans=0;
		for(int i=1;i<=n;i++) if(re[a[i]]==re[c[i]]) ans++;
		printf("%d\n",ans);
	}
    return 0;
}