#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;

vector<vi> triplets;

const int N = 1e5;

int A[N + 1], pf[729][6561], cnt[N + 1][8], L[729];

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;
    }

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

    ll ans = 0;
    rep(i, 1, n + 1) {
        pos[A[i]].push_back(i);
        for (auto &triplet : triplets) {
            vi need(8);
            int l = i;
            rep(j, 0, 6) {
                need[j] += triplet[j];
                need[j + 1] += triplet[j];
                need[j + 2] += triplet[j];
            }

            rep(j, 0, 8) {
                if (need[j] > cnt[i][j])
                    l = 0;
                else if (need[j])
                    l = min(l, pos[j][pos[j].size() - need[j]]);
            }

            if (l) {
                int x = decode(triplet);
                while (L[x] + 1 < l) {
                    L[x]++;
                    vi cur(8);
                    rep(j, 0, 8)
                        cur[j] = cnt[L[x]][j] % 3;
                    pf[x][decode(cur)]++;
                }

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

                ans += pf[x][decode(need)];
            }
        }
    }

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    rep(i, 0, 729) {
        vi nums(6);
        int mask = i;
        rep(j, 0, 6) {
            nums[j] = mask % 3;
            mask /= 3;
        }

        triplets.push_back(nums);
    }

    int t; cin >> t;
    while (t--)
        solve();
}