#include<bits/stdc++.h>
using namespace std;
#define LL long long int
LL solve(LL val,vector<LL> *div,unordered_map<LL,LL> &hash,LL &mn,vector<LL> &dp)
{
	if(hash[val]==0)
	{
		return 0;
	}
	if(dp[val]!= -1)
	{
		return dp[val];
	}
	LL a=0;
	for(auto it:div[val])
	{	
		if(it!=val)
		{
			a=max(a,solve(it,div,hash,mn,dp));
		}
	}
	return dp[val]=a + hash[val] ;
}
int main()
{ 
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	LL M= 2*100011;
	vector <LL> div[M+10];
	auto Sieve =[](vector<LL> *div,LL &M)
    {
    	for(LL i=1;i<=M;i++)
    	{
    		for(LL j=2;j*j<=i;j++)
    		{
    			if(i%j==0)
    			{
    				div[i].push_back(j);
    				if(j!=i/j)
    				div[i].push_back(i/j);
    			}
    		}
    	}
    };
    Sieve(div,M);
	LL T;
	cin >> T;
	while(T--)
	{
		LL N;
		cin >> N;
		vector<LL> arr(N);
		for(auto &it:arr)
		{
			cin >> it;
		}
		vector<LL> dp(M+1,-1);
		unordered_map <LL,LL> hash;
		vector<LL> pass;
		for(auto it:arr)
		{
			hash[it]++;
		}
		for(auto it:hash)
		{
			if(it.first>1)
			{
				pass.push_back(it.first);
			}
		}
		if(pass.size()==0)
		{
			cout<<0<<endl;
			continue;
		}
		LL mn= *pass.begin();
		LL M=1;
		reverse(pass.begin(),pass.end());
		for(auto it:pass)
		{
			M=max( M,solve(it,div,hash,mn,dp));
		}
		cout<< N- ( M + hash[1] ) << "\n";
	}
}