#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define sz(a) (int) (a).size()
#define forn(i, n) for(int i = 0; i < (n); i++)
#define int long long
using namespace std;

typedef long long ll;
typedef unsigned long long ULL;

const ULL A = 525523;

const int N = 2e5 + 11;
ULL h[N], pw[N], a[N];

ULL f(int l, int sz){
    return h[l + sz] - h[l] * pw[sz];
}

bool in(int l, int r, int x){
    return l <= x && x <= r;
}

struct update{
    int pos, i, type;
    int a, b, c;
};
vector<update> U;
void add(int i, int pos, int type, int a, int b = 0, int c = 0){
#ifdef LOCAL
    cout << "ADD " << i << ' ' << pos << ' ' << type << ' ' << a << ' ' << b << ' ' << c << endl;
#endif
    U.push_back({pos, i, type, a, b, c});
}

struct state{
    int t, a, b;
} ST[N];

int n;
int LCS(int a, int b){
    int ans = 0;
    for(int j = 19; j >= 0; j--){
        if(max(a, b) + (1 << j) > n) continue;
        if(f(a, 1 << j) == f(b, 1 << j))
            ans += (1 << j), a += (1 << j), b += (1 << j);
    }
    return ans;
}

void solve(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    fill(ST, ST + n + 1, state{0, 0});
    U.clear();
    h[0] = 0; for(int i = 0; i < n; i++) h[i + 1] = h[i] * A + a[i];
    for(int i = 1; i < n; i++){
        int L = 0, R = 0;
        for(int j = 19; j >= 0; j--){
            if(i + L + (1 << j) <= n && f(L, 1 << j) == f(i + L, 1 << j))
                L += (1 << j);
        }
        for(int j = 19; j >= 0; j--){
            if(i + L + 1 + R + (1 << j) <= n && f(L + 1 + R, 1 << j) == f(i + L + 1 + R, 1 << j))
                R += (1 << j);
        }

        vector<int> sp {0, L, L + 1, L + 1 + R, i, i + L, i + L + 1, i + L + R + 1};
        sort(sp.begin(), sp.end());
        sp.resize(unique(all(sp)) - sp.begin());
        while(!sp.empty() && sp.back() >= n) sp.pop_back();
        for(auto pos : sp){
            int pA = -1, pB = -1;
            if(in(0, L - 1, pos)) pA = 0;
            else if(in(L, L, pos)) pA = 1;
            else if(in(L + 1, L + R, pos)) pA = 2;

            if(in(i + 0, i + L - 1, pos)) pB = 0;
            else if(in(i + L, i + L, pos)) pB = 1;
            else if(in(i + L + 1, i + L + R, pos)) pB = 2;

            if((pA & 2) && (pB & 2)){
                add(i, pos, 1, L, 0);
            }else if(pA == -1){
                if(pB == 0){
                    add(i, pos, 1, pos - i, 1);
                }else if(pB == 1){
                    // cout << pos << ' ' << L + 1 + R << ' ' << a[pos] << ' ' << a[i + pos] << endl;
                    if(pos != L + 1 + R || i + pos >= n || a[L] != a[i + pos]){
                        add(i, pos, 2, a[L], L + 1 + R, L);
                    }else{
                        // cout << "???" << endl;
                        add(i, pos, 2, a[L], L + 1 + R + 1 + LCS(L + 1 + R + 1, i + L + 1 + R + 1), L);
                        // cout << "SPECIAL!" << endl;
                        // cout << pos << ' ' << L << ' ' << 1 + R + 1 << ' ' << LCS(L + 1 + R + 1, i + L + 1 + R + 1) << endl;
                    }
                }
            }else if(pB == -1){
                if(pA == 0){
                    add(i, pos, 1, pos, 1);
                }else if(pA == 1){
                    add(i, pos, 2, a[i + L], L + 1 + R, L);
                }
            }else if(pB == 0){
                add(i, pos, 1, pos - i, 1);
            }else if(pA == 2 && pB == 1){
                add(i, pos, 2, a[L], pos, L);
            }else{
                assert(false);
            }
        }
        // cout << i << ": " << L << ' ' << R << endl;
    }

    sort(all(U), [](auto& x, auto& y){
        return x.pos < y.pos;
    });
    int uid = 0;
    
    int x = 0, dx = 0;
    int xor_sum = 0;
    for(int pos = 0; pos < n; pos++){
        unordered_map<int, int> mp;
    #ifdef LOCAL
        cout << "POS = " << pos << endl;
    #endif
        while(uid < sz(U) && U[uid].pos == pos){
            auto& u = U[uid++];
            x -= ST[u.i].a + ST[u.i].b * (pos - ST[u.i].t), dx -= ST[u.i].b;
            ST[u.i] = state{0, 0, 0};
            if(u.type == 1){
                // cout << "GRADIENT " << u.i << ' ' << u.a << ' ' << u.b << endl;
                x += u.a; dx += u.b;
                ST[u.i] = state{pos, u.a, u.b};
            }else{
                // cout << "CHANGE " << u.i << ' ' << u.a << ' ' << u.b << ' ' << u.c << endl;
                x += u.c;
                ST[u.i] = state{pos, u.c, 0};
                mp[u.a] += u.b - u.c;
            }
        }
        int ans = n + x, mx = 0;
        for(auto [a, b] : mp){
            if(a == 0) continue;
            // cout << a << " => " << b << endl;
            mx = max(mx, b);
        }
        ans += mx;
        xor_sum += (ans ^ (pos + 1));
        x += dx;
#ifdef LOCAL
        cout << "POS = " << pos << ", " << "ANS = " << ans << '\n';
#endif
    }
    cout << xor_sum << '\n';
}

int32_t main(){
    pw[0] = 1; for(int i = 1; i < N; i++) pw[i] = pw[i - 1] * A;
    cin.tie(0)->sync_with_stdio(false);
    int t; cin >> t;
    while(t--){
        solve();
    }
}