CF1731C

// Problem: C. Even Subarrays
// Contest: Codeforces - Codeforces Round 841 (Div. 2) and Divide by Zero 2022
// URL: https://codeforces.com/problemset/problem/1731/C
// Memory Limit: 256 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

namespace rngs = std::ranges;
using ll = long long;
using a2l = array<ll, 2>;
using pll = pair<ll, ll>;
using vl = vector<ll>;

void solve()
{
    ll n;
    cin >> n;
    vl a(n);
    for (auto &x : a)
        cin >> x;

    ll tot = n * (n + 1) / 2, sub = 0;
    vl cnt(2 * n);
    cnt[0] = 1;

    for (ll i = 0, sum = 0; i < n; ++i) {
        sum = sum ^ a[i];
        for (ll j = 0; j * j < 2 * n; ++j) {
            ll tg = sum ^ (j * j);
            /*
            // TLE with cnt a map
            if (cnt.count(tg))
                dbg(tg, sum, j * j, cnt[tg]), sub += cnt[tg];
            */
            if (tg < 2 * n)
                sub += cnt[tg];
        }
        cnt[sum] += 1;
    }

    dbg(tot, sub);
    cout << tot - sub << '\n';
}

int main(int argc, char **argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ll t;
    cin >> t;
    while (t--)
        solve();

    return 0;
};