RT

#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define D double
#define LD long double
#define LL long long
#define ULL unsigned long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
namespace Dinic
{
    const int N = 5e6 + 7, M = 1e6 + 7;
    const LL inf = 1e18;
    int n, S, T, h[N], hi[N], e[M], t[M], tot, d[N];
    LL mxf, f[M];
    inline void add(int x, int y, LL z, int o = 1)
    {
        e[++tot] = y, f[tot] = z, t[tot] = h[x], h[x] = tot;
        if (o)
        {
            add(y, x, 0, 0);
        }
        return;
    }
    inline bool bfs()
    {
        for (int i = 1; i <= n; i++)
        {
            d[i] = 0;
        }
        queue<int> q;
        q.push(S), d[S] = 1;
        while (q.size())
        {
            int x = q.front();
            q.pop();
            for (int i = h[x]; i; i = t[i])
            {
                int y = e[i];
                LL z = f[i];
                if (d[y] || !z)
                {
                    continue;
                }
                q.push(y);
                d[y] = d[x] + 1;
                if (y == T)
                {
                    return 1;
                }
            }
        }
        return 0;
    }
    LL dinic(int x, LL nwf)
    {
        if (x == T)
        {
            return nwf;
        }
        LL rst = nwf;
        for (int &i = hi[x]; i; i = t[i])
        {
            int y = e[i];
            LL z = f[i];
            if (d[y] != d[x] + 1 || !z)
            {
                continue;
            }
            LL k = dinic(y, min(z, rst));
            if (!k)
            {
                d[y] = 0;
            }
            else
            {
                f[i] -= k;
                f[i ^ 1] += k;
                rst -= k;
            }
            if (!rst)
            {
                break;
            }
        }
        return nwf - rst;
    }
    inline void main()
    {
        while (bfs())
        {
            for (int i = 1; i <= n; i++)
            {
                hi[i] = h[i];
            }
            LL now;
            while ((now = dinic(S, inf)))
            {
                mxf += now;
            }
        }
        return;
    }
    inline void init(int _n, int _S, int _T)
    {
        n = _n, S = _S, T = _T, tot = 1, mxf = 0;
        for (int i = 1; i <= n; i++)
        {
            h[i] = 0;
        }
        return;
    }
}
int a[50010];
int pos[50010];

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        Dinic::init(4 * n + 2, 4 * n + 1, 4 * n + 2);
        int S = 4 * n + 1, T = 4 * n + 2;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            pos[a[i]] = i;
            Dinic::add(S, i, 1);
            Dinic::add(i + n, i + n + n, 1);
            Dinic::add(i + 3 * n, T, 1);
        }
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= a[n]; i++)
        {
            if (!pos[i])
            {
                continue;
            }
            for (int j = 2 * i; j <= a[n]; j += i)
            {
                if (pos[j])
                {
                    Dinic::add(pos[j], pos[i] + n, 0X3f3f3f3f);
                    Dinic::add(pos[j] + 2 * n, pos[i] + 3 * n, 0x3f3f3f3f);
                }
            }
        }
        Dinic::main();
        cout << Dinic::mxf << '\n';
        for (int i = 1; i <= n; i++)
        {
            pos[a[i]] = 0;
        }
    }
    return 0;
}