1475G - Strange Beauty

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int solve(vi a)
{
    int const AMAX = *max_element(begin(a), end(a)) + 1, n = a.size();
    vi dp(AMAX, 0), cnt(AMAX, 0);
    for (auto ai : a)
        cnt[ai]++;
    for (int x = 1; x < AMAX; ++x)
    {
        dp[x] += cnt[x];
        for (int y = 2 * x; y < AMAX; y += x)
            dp[y] = max(dp[y], dp[x]);
    }
    return n - *max_element(begin(dp), end(dp));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi a(n);
        for (auto &ai : a)
            cin >> ai;
        cout << solve(a) << endl;
    }
    return 0;
}