d.cpp

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 10;
int cnt[MAXN], a[MAXN], s[MAXN], kk[MAXN];
void solve(){

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++){
        cnt[i] = 0;
        s[i] = 0;
        kk[i] = 0;
    }

    for (int i = 1; i <= n; i++){
        cin >> a[i];
        cnt[a[i]]++;
    }
    sort(a + 1, a + n + 1);
    int c = 0;/*
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            for (int k = 1; k <= n; k++){
                if (a[i] % a[k] == 0 && a[j] % a[k] == 0){
                    c++;
                    cout << "@@@ c = " << c << ": " << a[i] << ' ' << a[j] << ' ' << a[k] << endl;
                    break;
                }
            }
        }
    }*/

    ll ans = n * (n - 1LL) / 2;
    ll ans2 = 0;
    //cout << "ans = " << ans << endl;
    for (int i = 1; i <= n; i++){
        if (cnt[i] == 0 && kk[i] == 0){
            continue;
        }
        ll k = 0;
        for (int j = i; j <= n; j += i){
            kk[j]++;
            k += cnt[j];
        }
        //cout << i << ' ' << s[i] << ' ' << cnt[i] << ' ' << k << endl;
        ans -= (1 - s[i]) * k * (k - 1) / 2;
        ans2 += (1 - s[i]) * k * (k - 1) / 2;
       // cout << "ans = " << ans << endl;
        int tmp = (1 - s[i]);
        for (int j = i; j <= n; j += i){
            s[j] += tmp;
        }
    }
    cout << ans << "\n";
}
/*
1
4
2 4 4 4

*/

int main() {
    IOS;
    int t = 1;
    cin >> t;

    while(t--){
        solve();
    }
    return 0;
}