考虑建立有向图 $G$，满足若 $a_i\mid a_j$，则有边 $j\rarr i$，容易发现原题要求的即为在 $G$ 上至少删去多少个点使得每个点只有入边或者只有出边。

证明：若 $G$ 中存在边 $y\rarr x\rarr z$，则有边 $y\rarr z$，在原题的图上存在奇环 $(x,y,z)$。若 $G$ 中不存在点既有入边又有出边，则该图显然为二分图。

我们将问题转化为求解保留最多的点使得其为二分图。

先考虑这样一个问题，在 $G$ 中选择最多数量的点使得互相之间没有连边。

这是一个经典问题，因为 $G$ 是偏序集，根据 Dilworth 定理，我们有最长反链等于最小链覆盖，所以直接跑最小链覆盖就好了。

这给了我们启发，我们对于每个点 $u$ 建立点 $u’$，若存在边 $u\rarr v$，则连接 $u’\rarr v,u’\rarr v’$，并连接 $u’\rarr u$，容易发现这也是个偏序集，并且其最长反链即为答案。

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<numeric>
using std::cin;
using std::cout;
int S,T,cnt,cur[200010],head[200010],to[4000010],nxt[4000010],w[4000010],ecnt;
void add(int x,int y){
	to[++ecnt]=y,nxt[ecnt]=head[x],head[x]=ecnt,w[ecnt]=1;
	to[++ecnt]=x,nxt[ecnt]=head[y],head[y]=ecnt,w[ecnt]=0;
}
int d[200010];
bool bfs(){
	for(int i=1;i<=cnt;i++) d[i]=0;
	d[S]=1;
	static int que[200010];
	int *hd=que,*tl=que;
	*tl++=S;
	while(hd!=tl){
		int x=*hd++;
		for(int i=head[x];i;i=nxt[i]) if(!d[to[i]]&&w[i]) d[to[i]]=d[x]+1,*tl++=to[i];
	}
	return d[T];
}
int dfs(int x,int flow){
	if(x==T) return flow;
	int used=0;
	for(int &i=cur[x];i;i=nxt[i])if(w[i]&&d[x]==d[to[i]]-1){
		int v=dfs(to[i],std::min(w[i],flow-used));
		w[i]-=v,w[i^1]+=v,used+=v;
		if(flow==used) return flow;
	}
	return used;
}
int dinic(){
	int ans=0;
	while(bfs()){
		for(int i=1;i<=cnt;i++) cur[i]=head[i];
		ans+=dfs(S,1e7);
	}
	return ans;
}
int n,a[50010],id[50010][2][2],trans[50010];
void solve(){
	cin>>n;
	for(int i=1;i<=50000;i++) trans[i]=0;
	for(int i=1;i<=n;i++) cin>>a[i],trans[a[i]]=i;
	cnt=0;
	S=++cnt,T=++cnt;
	for(int i=1;i<=n;i++) id[i][0][0]=++cnt,id[i][0][1]=++cnt,id[i][1][0]=++cnt,id[i][1][1]=++cnt;
	for(int i=1;i<=cnt;i++) head[i]=0;
	ecnt=1;
	for(int i=1;i<=n;i++) add(S,id[i][0][0]),add(S,id[i][1][0]),add(id[i][0][1],T),add(id[i][1][1],T),add(id[i][1][0],id[i][0][1]);
	for(int a=1;a<=50000;a++) if(trans[a])
		for(int b=a+a;b<=50000;b+=a) if(trans[b]){
			int i=trans[b],j=trans[a];
			add(id[i][0][0],id[j][0][1]),add(id[i][1][0],id[j][0][1]),add(id[i][1][0],id[j][1][1]);
		}
	cout<<(-n+dinic())<<'\n';
}
int main(){
	std::ios::sync_with_stdio(false),cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}