#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(x) x.begin(), x.end()
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;

const int N = 1e5;

const int p[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561};
int A[N + 1], code[N + 1], pf[729][6561], cnt[N + 1][8], L[729], need[729][8];

vi pos[8];

int decode(vi &nums) {
    int mask = 0;
    for (auto d : nums)
        mask = 3 * mask + d;

    return mask;
}

void solve() {
    int n; cin >> n;
    rep(i, 0, 8) pos[i] = {0, 0, 0, 0};
    memset(cnt, 0, sizeof cnt);
    memset(L, 0, sizeof L);
    
    rep(i, 1, n + 1) {
        cin >> A[i];
        A[i]--;
        rep(j, 0, 8)
            cnt[i][j] = cnt[i - 1][j];
        cnt[i][A[i]]++;
        vi cur(8);
        rep(j, 0, 8) cur[j] = cnt[i][j] % 3;
        int x = decode(cur);
        rep(j, 0, 729)
            pf[j][x] = 0;

        code[i] = x;
    }

    rep(i, 0, 729)
        pf[i][0] = 1;

    ll ans = 0;
    rep(i, 1, n + 1) {
        pos[A[i]].push_back(i);
        for (int triplet = 0; triplet < 729; triplet++) {
            int l = i;
            rep(j, 0, 8) {
                if (need[triplet][j] > cnt[i][j])
                    l = 0;
                else if (need[triplet][j])
                    l = min(l, pos[j][pos[j].size() - need[triplet][j]]);
            }

            if (l) {
                while (L[triplet] + 1 < l) {
                    L[triplet]++;
                    pf[triplet][code[L[triplet]]]++;
                }

                vi m(8);
                rep(j, 0, 8)
                    m[j] = (cnt[i][j] - need[triplet][j]) % 3;

                ans += pf[triplet][decode(m)];
            }
        }
    }

    cout << ans << "\n";
    
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    for (int triplet = 0; triplet < 729; triplet++) {
        rep(j, 0, 6) {
            int val = triplet / p[j] % 3;
            need[triplet][j] += val;
            need[triplet][j + 1] += val;
            need[triplet][j + 2] += val;
        }
    }
    int t; cin >> t;
    while (t--)
        solve();
}