#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define elif else if
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define pii pair<int, int>

#define repname(a, b, c, d, e, ...) e
#define rep(...) repname(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define rep0(x) for (int rep_counter = 0; rep_counter < (x); ++rep_counter)
#define rep1(i, x) for (int i = 0; i < (x); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rep3(i, l, r, c) for (int i = (l); i < (r); i += (c))

struct ScalarInput {
  template <class T>
  operator T() {
    T ret;
    cin >> ret;
    return ret;
  }
};
struct VectorInput {
  size_t n;
  VectorInput(size_t n) : n(n) {}
  template <class T>
  operator vector<T>() {
    vector<T> ret(n);
    for (T& x : ret) cin >> x;
    return ret;
  }
};
ScalarInput input() { return ScalarInput(); }
VectorInput input(size_t n) { return VectorInput(n); }

template <typename T>
void print(vector<T> a) {
  for (int i = 0; i < a.size(); i++) {
    cout << a[i] << " \n"[i + 1 == a.size()];
  }
}

template <class T>
void print(T x) {
  cout << x << '\n';
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  cout << head << ' ';
  print(forward<Tail>(tail)...);
}

vi sa_is(vi& s, int up) {
  int n = s.size();
  if (n == 0) return {};
  vi sa(n), ls(n), sml(up + 1), sms(up + 1);
  for (int i = n - 2; i >= 0; i--) {
    ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
  }
  rep(i, n) {
    if (!ls[i])
      sms[s[i]]++;
    else
      sml[s[i] + 1]++;
  }
  rep(i, up + 1) {
    sms[i] += sml[i];
    if (i < up) sml[i + 1] += sms[i];
  }

  auto induce = [&](vi& lms) {
    rep(i, n) sa[i] = -1;
    vi buf = sms;
    for (auto d : lms) {
      if (d == n) continue;
      sa[buf[s[d]]++] = d;
    }
    // print(sa); // -1 1 4 7 -1 -1 -1 -1 -1 -1 -1 (mississippi の例)
    buf = sml;
    sa[buf[s[n - 1]]++] = n - 1;
    rep(i, n) {
      int v = sa[i];
      if (v >= 1 && !ls[v - 1]) sa[buf[s[v - 1]]++] = v - 1;
    }
    // print(sa); // 10 1 4 7 0 9 8 3 6 2 5

    buf = sml;
    for (int i = n - 1; i >= 0; i--) {
      int v = sa[i];
      if (v >= 1 && ls[v - 1]) sa[--buf[s[v - 1] + 1]] = v - 1;
    }
    // print(sa); // 10 7 1 4 0 9 8 3 6 2 5
  };

  vi lms, mp(n + 1, -1);  // mp : lms の inverse
  int m = 0;
  rep2(i, 1, n) {
    if (!ls[i - 1] && ls[i]) {
      mp[i] = m++;
      lms.push_back(i);
    }
  }
  // print(mp); // -1 0 -1 -1 1 -1 -1 2 -1 -1 -1 -1

  induce(lms);

  if (m) {
    vi srt, rec(m);  // srt = sorted_lms
    for (auto v : sa) {
      if (mp[v] != -1) srt.push_back(v);
    }
    int tmp = 0;
    rec[mp[srt[0]]] = 0;
    rep2(i, 1, m) {
      int l = srt[i - 1], r = srt[i];
      int el = (mp[l] + 1 < m) ? lms[mp[l] + 1] : n;
      int er = (mp[r] + 1 < m) ? lms[mp[r] + 1] : n;
      bool same = true;
      if (el - l != er - r)
        same = false;
      else {
        while (l < el) {
          if (s[l] != s[r]) break;
          l++;
          r++;
        }
        if (l == n || s[l] != s[r]) same = false;
      }
      if (!same) tmp++;
      rec[mp[srt[i]]] = tmp;
    }
    // print(rec); // 1 1 0
    // print(srt); // 7 1 4
    vi rec_sa = sa_is(rec, tmp);

    rep(i, m) srt[i] = lms[rec_sa[i]];
    induce(srt);
  }
  return sa;
}

vi LCP(vi s, vi sa) {
  int n = s.size();
  vi rank(n), lcp(n - 1);
  rep(i, n) rank[sa[i]] = i;
  for (int i = 0, h = 0; i < n; i++) {
    if (rank[i] + 1 < n) {
      int j = sa[rank[i] + 1];
      while (max(i, j) + h < n && s[i + h] == s[j + h]) h++;
      lcp[rank[i]] = h;
      if (h > 0) --h;
    }
  }
  return lcp;
}

template <typename T>
struct SparseTable {
  using F = function<T(T, T)>;
  F op;
  vector<vector<T>> st;
  vi lookup;

  SparseTable(const vector<T>& v, const F& op) : op(op) {
    int n = v.size();
    int b = 0;
    while ((1 << b) <= n) b++;
    st.assign(b, vector<T>(n));
    rep(i, n) st[0][i] = v[i];

    for (int i = 1; i < b; i++) {
      for (int j = 0; j + (1 << i) <= n; j++) {
        st[i][j] = op(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
    lookup.resize(n + 1);
    for (int i = 2; i < lookup.size(); i++) {
      lookup[i] = lookup[i >> 1] + 1;
    }
  }

  T query(int l, int r) const {
    int b = lookup[r - l];
    return op(st[b][l], st[b][r - (1 << b)]);
  }
};

int op(int a, int b) { return min(a, b); }

void solve() {
  int n;
  cin >> n;
  vi a(n);
  rep(i, n) cin >> a[i];
  vi sa = sa_is(a, n);
  vi inv(n);
  rep(i, n) inv[sa[i]] = i;
  vi la = LCP(a, sa);
  SparseTable<int> st(la, op);

  auto calc = [&](int i, int j) -> int {
    if (i == j) return n - i;
    if (i >= n || j >= n) return 0;
    int posi = inv[i];
    int posj = inv[j];
    if (posi < posj) return st.query(posi, posj);
    return st.query(posj, posi);
  };

  ll init_ans = 0;
  vll d0(n + 1, 0), d1(n + 1, 0);
  vector<unordered_map<int, ll>> mp(n);
  rep(l, n) {
    int len = calc(0, l);
    int l1 = 0;
    int r1 = len;
    int l2 = l;
    int r2 = l + len;
    init_ans += len;

    if (l == 0) continue;

    if (r1 <= l2) {
      d0[l1] += -len;
      d1[l1] += 1;
      d1[r1] -= 1;

      d0[l2] += -len;
      d1[l2] += 1;
      d1[min(n, r2)] -= 1;
    }

    else {
      d0[l1] += -len;
      d1[l1] += 1;
      d1[r2] -= 1;
      d0[l2] -= l2 - l1;
    }

    if (l + len == n) continue;

    // 増加する可能性があるやつ

    int d = calc(len + 1, l + len + 1);

    // a[len] を a[l + len] に置き換える
    if (len < l2) {
      mp[len][a[l + len]] += d + 1;
    }
    // a[l + len] を a[len] に置き換える
    int d2 = min(l - 1, d);
    int pos1 = len + 1 + d2;
    int pos2 = l + len + 1 + d2;
    if (pos1 == l + len && pos2 < n && a[len] == a[pos2]) {
      int d3 = calc(pos1 + 1, pos2 + 1);
      mp[l + len][a[len]] += d2 + d3 + 2;
    } else {
      mp[l + len][a[len]] += d2 + 1;
    }
  }

  vll diff(n, 0);
  ll tmp0 = 0;
  ll tmp1 = 0;
  rep(i, n) {
    tmp0 += d0[i] + tmp1;
    diff[i] = tmp0;
    tmp1 += d1[i];
  }

  vll ans(n);
  rep(i, n) {
    ll mx = 0;
    for (auto [key, val] : mp[i]) {
      if (key != a[i]) mx = max(mx, val);
    }
    ans[i] = init_ans + diff[i] + mx;
  }
  ll ANS = 0;
  rep(i, n) ANS += (i + 1) ^ ans[i];
  print(ANS);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T;
  cin >> T;
  rep(T) solve();
}