D

#include <bits/stdc++.h>

using namespace std;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)

int main()
{
    _test
    {
        int n;
        cin>>n;

        vector<int> a(n+1);

        for(int i=1; i<=n; i++)
        {
            int x;
            cin>>x;
            a[x]++;
        }

        ll int ans = n*1ll*(n-1)/2;
        vector<ll int> f(n+1);

        for(int i=n; i>0; i--)
        {
            ll int m=0;
            for(int j=i; j<=n; j+=i)
            {
                m+=a[j];
                f[i]-=f[j];
            }

            f[i] += m*1ll*(m-1)/2;
        }

        for(int i=1; i<=n; i++)
        {
            if(a[i])
            {
                for(int j=i; j<=n; j+=i)
                {
                    ans-=f[j];
                    f[j]=0;
                }
            }
        }

        cout<<ans<<"\n";
    }
}