#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 2e5 + 1;

vector<int> factors[MAXN];
int dp[MAXN];

void prepare()
{
	for (int i = 2; i < MAXN; ++i)
		for (int j = 2*i; j < MAXN; j += i)
			factors[j].push_back(i);
}

void solve()
{
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	sort(a.begin(), a.end());
	int ans = 0;
	for (int i = 0; i < n; ++i)
	{
		int best = 1;
		int v = a[i];
		best = max(best, dp[1] + 1);
		best = max(best, dp[v] + 1);
		for (int j = 0; j < factors[v].size(); ++j)
		{
			int d = factors[v][j];
			best = max(best, dp[d] + 1);
		}
		dp[v] = best;
		ans = max(ans, best);
	}
	for (int i = 0; i < n; ++i)
		dp[a[i]] = 0;
	printf("%d\n", n - ans);
}

int main()
{
	prepare();
	int T;
	scanf("%d", &T);
	for (int i = 0; i < T; ++i)
		solve();
	return 0;
}
