#include <bits/stdc++.h>
         
        using namespace std;
         
        const int MaxN = (int)1e6 + 10;
        const int MOD = (int)1e9 + 7;
         
        int n, a[MaxN], pr[MaxN];
        int cnt[MaxN], d[MaxN];
        vector < int > v[MaxN];
         
        bool foo(int x, int y) {
        	return x % y == 0 && d[x] % d[y] == 0;
        }
         
        void solve() {
        	scanf("%d", &n);
        	map < int, int > cnt;
        	for (int i = 1; i <= n; ++i) {
        		scanf("%d", &a[i]);
        		cnt[a[i]]++;
        		assert (2 <= a[i] && a[i] <= 1e6);
        	}
        	long long ans = 0;
        	for (auto &it : cnt) {
        		ans += 1LL * it.second * (it.second - 1);
        		for (auto &jt : v[it.first]) {
        			if (cnt.count(jt)) {
        				ans += 1LL * it.second * cnt[jt];
        			}
        		}
        	}
        	printf("%lld\n", ans);
        }
         
        int main() {
        //	freopen("input.txt", "r", stdin);
        	for (int i = 2; i < MaxN; ++i) {
        		pr[i] = 1;
        	}
        	for (int i = 2; i < MaxN; ++i) {
        		if (pr[i]) {
        			for (int j = i; j < MaxN; j += i) {
        				d[j] += i;
        				pr[j] = 0;
        			}
        		}
        	}
        	for (int j = 2; j < MaxN; ++j) {
        		for (int i = 2 * j; i < MaxN; i += j) {
        			if (foo(i, j)) {
        				v[i].push_back(j);
        			}
        		}
        	}
        	int t;
        	scanf("%d", &t);
        	while (t --> 0) {
        		solve();
        	}
        	return 0;
        }