#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define sz 2000008
#define f first
#define s second
int mod,arr[sz],brr[sz];
std::vector<ll> v,v1[sz];
int main()
{
  mod =1000000007;
  int t=1;
  scanf("%d",&t);
  while(t--)
  {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    	scanf("%d",&arr[i]);
    }
    sort(arr+1,arr+n+1);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
    	if(brr[arr[i]])
    	{
    		brr[arr[i]]++;
    		ans=max(ans,brr[arr[i]]);
    		continue;
    	}
    	brr[arr[i]]=1;
     for(int j=2;j*j<=arr[i];j++)
     {
     	if(arr[i]%j==0)
     	{
         int a=j;
         int b=arr[i]/j;
         brr[arr[i]]=max(brr[arr[i]],max(brr[a],brr[b])+1);
     	}
     }
     if(arr[i]!=1)
     brr[arr[i]]=max(brr[arr[i]],brr[1]+1);
     ans=max(ans,brr[arr[i]]);
    }
    printf("%d\n",n-ans);
    for(int i=1;i<=n;i++)
    	brr[arr[i]]=0;
  }
}
