#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define sz(s) (int)(s).size()
#define all(s) s.begin(), s.end()

void Speed(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
const int N = (1<<20) + 1;
int mob[N];
bool prime[N];
vector<int> d[N];
void moebius(){
    fill(mob, mob + N, 1);
    memset(prime + 2, 1, sizeof(prime) - 2);
    mob[0] = 0;
    mob[2] = -1;
    for (int i = 4; i < N; i += 2){
        mob[i] *= (i & 3) ? -1 : 0;
        prime[i] = 0;
    }
    for (int i = 3; i < N; i += 2){
        if (prime[i]){
            mob[i] = -1;
            for (int j = 2 * i; j < N; j += i){
                mob[j] *= j % (1LL * i * i) ? -1 : 0;
                prime[j] = 0;
            }
        }
    }

    for(int i = 2; i < N; i++){
        if(mob[i] == 0) continue;
        for(int j = i; j < N; j += i){
            d[j].push_back(i);
        }
    }
}

int freq[N];

void solve(){
    int n; cin >> n;
    vector<int> a(n);
    for(auto& it : a) cin >> it;
    ll ans = 0;
    for(int i = 0; i < n; i++){
        int cnt_non_zero = 0, cnt_zero = 0;
        vector<int> upd;
        for(int j = i + 1; j < n; j++){
            int x = (a[i] ^ a[j]);
            if(x == 0){
                cnt_zero++;
                continue;
            }
            for(int y : d[x]){
                ans -= 1ll * mob[y] * freq[y];
                freq[y]++;
                upd.push_back(y);
            }
            if(x > 1) cnt_non_zero++;
        }
        ans+=1LL*cnt_non_zero*cnt_zero;
        for(int x : upd) freq[x] = 0;
    }
    cout << ans << '\n';
}

int main(){
    freopen("gcd.in", "r", stdin);
    Speed();
    moebius();
    int tc = 1;
    cin >> tc;
    while (tc--){
        solve();
    }
    return 0;
}