#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int maxn=500005*4;

int n;

int Max=0;

struct edge{

	int to,next;

}e[maxn];int head[maxn],cnt=0;

void add(int x,int y){

	e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;

}

int w[maxn],b[maxn];

int dfn[maxn],low[maxn],dfs_clock,sta[maxn],top,belong[maxn],siz[maxn],vis[maxn],dcc;

void dfs(int u){

	dfn[u]=low[u]=++dfs_clock;

	sta[++top]=u;

	for(int i=head[u];i;i=e[i].next){

		int v=e[i].to;

		if(!dfn[v]){

			dfs(v);

			low[u]=min(low[u],low[v]);

		}

		else if(!belong[v]){

			low[u]=min(low[u],dfn[v]);

		}

	}

	if(dfn[u]==low[u]){//特殊的出栈方式

		dcc++;

		belong[u]=dcc;

		siz[dcc]++;

		while(sta[top]!=u){

			int x=sta[top--];

			belong[x]=dcc;

			siz[dcc]++;

			vis[x]=1;

		}

		if(siz[dcc]>1)vis[u]=1;

		top--;

	}

}

void clear(){

	memset(e,0,sizeof(e));

	memset(head,0,sizeof(head));

	cnt=0;Max=0;

	memset(w,0,sizeof(w));

	memset(b,0,sizeof(b));

	memset(dfn,0,sizeof(dfn));

	memset(low,0,sizeof(low));

	dfs_clock=0;

	memset(sta,0,sizeof(siz));

	top=0;

	memset(belong,0,sizeof(belong));

	memset(siz,0,sizeof(siz));

	memset(vis,0,sizeof(vis));

	dcc=0;

}

int main(){

	//freopen("a.in","r",stdin);

	int t;scanf("%d",&t);

	while(t--){

		scanf("%d",&n);

		for(int i=1;i<=n;i++){

			scanf("%d",&w[i]);

			add(n+w[i],i);

			Max=max(Max,w[i]);//建第一种边

		}

		for(int i=1;i<=n;i++){

			scanf("%d",&b[i]);

			add(i,n+b[i]);//见第二种边

		}

		for(int i=1;i<=Max;i++){

			for(int j=2;j*i<=Max;j++){//第三种边

				add(i+n,j*i+n);

			}

		}

		if(n==1){//数据特判，详见样例1

			printf("1\n");clear();continue;

		}

		for(int i=1;i<=n;i++){//tarjan

			if(!dfn[i])dfs(i);

		}

		int ans=0;

		for(int i=1;i<=n;i++){//判断答案，注意只要1——n的点

			if(vis[i])ans++;

		}

		printf("%d\n",ans);

		clear();

	}

	return 0;

}