#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int n, a[MAXN];
int cnt[MAXN], s[MAXN], used[MAXN];
vector <int> v[MAXN];
int main() {
for (int i = 2; i < MAXN; ++i) {
if(s[i] == 0) {
for (int j = i; j < MAXN; j += i) {
s[j] += i;
}
}
}
for (int j = 2; j < MAXN; ++j) {
for (int i = 2 * j; i < MAXN; i += j) {
if(s[i] % s[j] == 0) {
v[i].push_back(j);
}
}
}
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
cnt[a[i]]++;
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
if(!used[a[i]]) {
ans += 1ll * cnt[a[i]] * (cnt[a[i]] - 1);
for (auto j : v[a[i]]) {
ans += 1ll * cnt[a[i]] * cnt[j];
}
used[a[i]]=1;
}
}
for(int i = 1; i <= n; i++) {
used[a[i]] = 0;
cnt[a[i]] = 0;
}
printf("%lld\n", ans);
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIApjb25zdCBpbnQgTUFYTiA9IDFlNiArIDEwOwogCmludCBuLCBhW01BWE5dOwppbnQgY250W01BWE5dLCBzW01BWE5dLCB1c2VkW01BWE5dOwp2ZWN0b3IgPGludD4gdltNQVhOXTsKIAppbnQgbWFpbigpIHsKCWZvciAoaW50IGkgPSAyOyBpIDwgTUFYTjsgKytpKSB7CgkJaWYoc1tpXSA9PSAwKSB7CgkJCWZvciAoaW50IGogPSBpOyBqIDwgTUFYTjsgaiArPSBpKSB7CgkJCQlzW2pdICs9IGk7CgkJCX0KCQl9Cgl9Cglmb3IgKGludCBqID0gMjsgaiA8IE1BWE47ICsraikgewoJCWZvciAoaW50IGkgPSAyICogajsgaSA8IE1BWE47IGkgKz0gaikgewoJCQlpZihzW2ldICUgc1tqXSA9PSAwKSB7CgkJCQl2W2ldLnB1c2hfYmFjayhqKTsKCQkJfQoJCX0KCX0KCWludCB0OwoJc2NhbmYoIiVkIiwgJnQpOwoJd2hpbGUgKHQtLSkgewoJCXNjYW5mKCIlZCIsICZuKTsKCQlmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kpIHsKCQkJc2NhbmYoIiVkIiwgJmFbaV0pOwoJCQljbnRbYVtpXV0rKzsKCQl9CgkJbG9uZyBsb25nIGFucyA9IDA7CgkJZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CgkJCWlmKCF1c2VkW2FbaV1dKSB7CgkJCQlhbnMgKz0gMWxsICogY250W2FbaV1dICogKGNudFthW2ldXSAtIDEpOwoJCQkJZm9yIChhdXRvIGogOiB2W2FbaV1dKSB7CgkJCQkJYW5zICs9IDFsbCAqIGNudFthW2ldXSAqIGNudFtqXTsKCQkJCX0KCQkJCXVzZWRbYVtpXV09MTsKCQkJfQoJCX0KCQlmb3IoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewoJCQl1c2VkW2FbaV1dID0gMDsKCQkJY250W2FbaV1dID0gMDsKCQl9CgkJcHJpbnRmKCIlbGxkXG4iLCBhbnMpOwoJfQp9ICA=