#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T& t){
	t=0; register char ch=getchar(); register int fflag=1;
	while(!('0'<=ch&&ch<='9')){if(ch=='-') fflag=-1;ch=getchar();}
	while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;
}
template <typename T,typename... Args> inline void read(T& t, Args&... args){read(t);read(args...);}
const int N=1e5+5;
int T,n,head[N],etot,tcnt;
int jbw[N],sb[N];
struct edge{
	int to,Next;
	void add(int _t,int _n){
		to=_t,
		Next=head[_n],
		head[_n]=etot;
	}
	void clear(){
		to=0,Next=0;
	}
}e[int(3e6)];
stack<int> st;
int sd[N],dfn[N],low[N];
bool vis[N];
int tarjan(int p){
	dfn[p]=low[p]=++tcnt;
	vis[p]=1;
	st.push(p);
	for(int i=head[p];i;i=e[i].Next){
		int v=e[i].to;
		if(!dfn[v]){	
			tarjan(v);
			low[p]=min(low[v],low[p]);
		}
		else if(vis[v])low[p]=min(low[p],low[v]);
	}
	if(dfn[p]==low[p]){
		int v;
		while(!st.empty()){
			v=st.top();
			sd[v]=p;
			vis[v]=0;
			st.pop();
			if(p==v)break;
		}		
	}
}
int main(){
	read(T);
	while(T--){
		memset(jbw,0,sizeof(jbw));
		memset(sb,0,sizeof(sb));
		memset(sd,0,sizeof(sd));
		memset(low,0,sizeof(low));
		memset(dfn,0,sizeof(dfn));
		memset(head,0,sizeof(head));

		etot=tcnt=0;
		read(n);
		for(int i=1;i<N;++i)
			for(int j=2;j*i<N;++j)
				e[++etot].add(i*j,i);
		for(int i=1;i<=n;++i)
			read(jbw[i]);
		for(int i=1;i<=n;++i)
			read(sb[i]),e[++etot].add(sb[i],jbw[i]);
		for(int i=1;i<N;i++)if(!dfn[i])tarjan(i);
		int ans=0;
		for(int i=1;i<=n;++i)if(sd[jbw[i]]==sd[sb[i]]){
			ans++;
		}
		printf("%d\n",ans);
	}
}

自己造数据和题解对拍都对的，但是全是RE