实在玄学，查了一个晚上了

//链式前向星

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int dfn[N],low[N],col[N],tim;
int stk[N],top,n,c;
int w[N],e[N];
int to[N],nxt[N],head[N],cnt;
//vector<int>g[N];
void add(int u,int v)
{
	to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
	//g[u].push_back(v);
}
void tarjan(int u)
{
	low[u]=dfn[u]=++tim;
	stk[++top]=u;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(!col[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		col[u]=++c;
		while(stk[top]!=u)col[stk[top--]]=c;
		--top;
	}
}
void init()
{
	tim=c=top=cnt=0;
	memset(col,0,sizeof col);
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
	memset(head,0,sizeof low);
	memset(nxt,0,sizeof low);
	memset(to,0,sizeof low);
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		
		cin>>n;
		init();
		for(int i=1;i<=n;++i)cin>>w[i];
		for(int i=1;i<=n;++i)cin>>e[i];
		for(int i=1;i+i<N;++i)
			for(int j=2;j*i<N;++j)
				add(i,i*j);
		for(int i=1;i<=n;++i)add(w[i],e[i]);
		for(int i=1;i<N;++i)if(dfn[i]==0)tarjan(i);
		int ans=0;
		for(int i=1;i<=n;++i)if(col[w[i]]==col[e[i]])ans++;
		cout<<ans<<endl;
	}
}

//vector

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int dfn[N],low[N],col[N],tim;
int stk[N],top,n,c;
int w[N],e[N];
vector<int>g[N];
void add(int u,int v)
{
	g[u].push_back(v);
}
void tarjan(int u)
{
	//cout<<u<<endl;
	low[u]=dfn[u]=++tim;
	stk[++top]=u;
	for(int i=0;i<g[u].size();i++)
	{
		//cout<<u<<" "<<to[i]<<endl;
		int v=g[u][i];
		if(dfn[v]==0)
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(col[v]==0)low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		col[u]=++c;
		while(stk[top]!=u)col[stk[top--]]=c;
		--top;
	}
}
void init()
{
	tim=c=top=0;
	for(int i=0;i<N;++i)g[i].clear();
	memset(col,0,sizeof col);
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		
		cin>>n;
		init();
		for(int i=1;i<=n;++i)cin>>w[i];
		for(int i=1;i<=n;++i)cin>>e[i];
		for(int i=1;i+i<N;++i)
			for(int j=2;j*i<N;++j)
				add(i,i*j);
		for(int i=1;i<=n;++i)add(w[i],e[i]);
		for(int i=1;i<N;++i)if(dfn[i]==0)tarjan(i);
		int ans=0;
		for(int i=1;i<=n;++i)if(col[w[i]]==col[e[i]])ans++;
		cout<<ans<<endl;
	}
}