/***
    Description: DP

   * author:    Diego Briaares
   * date:   26.01.2021 00:42:11
***/

#include <bits/stdc++.h>
using namespace std;
	int main () {
		ios_base::sync_with_stdio(0);
		cin.tie(0);
		int t;
		cin >> t;
		vector<vector<int>> divs(300000);
		for (int i = 1; i < 300000; i++) {
			for (int j = i + i; j < 300000; j += i) {
				divs[j].push_back(i);
			}
		}
		while (t--) {
			int n;
			cin >> n;
			vector<int> a(n);
			map<int, int> c;
			for (int i = 0; i < n; i++) {
				cin >> a[i];
				c[a[i]]++;
			}
			sort(a.begin(), a.end());
			vector<int> dp(a[n - 1] + 1);
			int ans = 0;
			for (int i = 1; i <= a[n - 1]; i++) {
				int  m = 0;
				for (auto y : divs[i]) {
					m = max(m, dp[y]);
				}
				if (c[i] > 0) dp[i] = c[i] + m;
				ans = max(ans, dp[i]);
			}
			cout << n - ans << "\n";
		}
	}