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

using ll = long long;
using ld = long double;

#define all(a) begin(a), end(a)
#define len(a) int((a).size())

const int N = 9;
int p3[N];
vector<array<int, 8>> v;

int at(int mask3, int pos) {
    return mask3 / p3[pos] % 3;
}

void precalc() {
    p3[0] = 1;
    for (int i = 1; i < N; i++) {
        p3[i] = p3[i - 1] * 3;
    }

    for (int mask = 0; mask < p3[6]; mask++) {
        array<int, 8> cur{};
        for (int i = 0; i < 6; i++) {
            int x = at(mask, i);
            for (int j : {i, i + 1, i + 2}) {
                cur[j] += x;
            }
        }
        v.push_back(cur);
    }
}

void solve(int /* test_num */) {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<array<int, 8>> pref(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        pref[i + 1] = pref[i];
        pref[i + 1][a[i]]++;
    }

    vector<int> pref_mask3(n + 1);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < 8; j++) {
            pref_mask3[i] += p3[j] * (pref[i][j] % 3);
        }
    }

    int cnt[p3[8]];
    ll ans = 0;
    for (auto lim : v) {
        memset(cnt, 0, sizeof(cnt));

        int j = n;
        int start = n - 1;

        for (int x = 0; x < 8; x++) {
            while (start >= 0 && pref[j][x] - pref[start][x] < lim[x]) {
                start--;
            }
        }
        if (start < 0) {
            continue;
        }

        int mapping[p3[8]];
        memset(mapping, 0, sizeof(mapping));
        for (int mask3 = 0; mask3 < p3[8]; mask3++) {
            for (int i = 0; i < 8; i++) {
                mapping[mask3] += ((at(mask3, i) + lim[i]) % 3) * p3[i];
            }
        }

        cnt[pref_mask3[n]]++;
        for (int i = start; i >= 0; i--) {
            while (j > i + 1 && pref[j][a[j - 1]] - pref[i][a[j - 1]] > lim[a[j - 1]]) {
                cnt[pref_mask3[--j]]++;
            }
            ans += cnt[mapping[pref_mask3[i]]];
        }
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    precalc();

    int tests;
    cin >> tests;
    for (int test_num = 1; test_num <= tests; test_num++) {
        solve(test_num);
    }
}