#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int a[N], d[9], c[9], tc[6561], f[N], sum[6561][6561];

signed main() {
    for (int i = 0; i < 6561; ++i) {
        for (int j = 0; j < 6561; ++j) {
            int ti = i, tj = j;
            for (int k = 1, pw = 1; k <= 8; ++k, pw *= 3) {
                int x = (ti % 3 + tj % 3) % 3;
                ti /= 3, tj /= 3;
                sum[i][j] += x * pw;
            }
        }
    }
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        for (int i = 1; i <= n; ++i) {
            f[i] = f[i - 1];
            int now = f[i];
            for (int j = 1, pw = 1; j <= 8; ++j, pw *= 3) {
                int x = now % 3;
                now /= 3;
                if (j == a[i]) {
                    if (x != 2) f[i] += pw;
                    else f[i] -= pw + pw;
                }
            }
        }
        long long res = 0;
        for (int i = 0; i < 729; ++i) {
            fill(d + 1, d + 9, 0), fill(c + 1, c + 9, 0);
            int ti = i;
            for (int j = 1; j <= 6; ++j) {
                int x = ti % 3;
                ti /= 3;
                d[j] += x, d[j + 1] += x, d[j + 2] += x;
            }
            int sta = 0, ok = count(d + 1, d + 9, 0), r = 1;
            for (int j = 1, pw = 1; j <= 8; ++j, pw *= 3) {
                sta += d[j] * pw;
            }
            ok += (++c[a[r]] == d[a[r]]);
            while (r < n && ok < 8) {
                ++r, ok += (++c[a[r]] == d[a[r]]);
            }
            if (ok < 8) continue;
            int l = 1;
            memset(tc, 0, sizeof(tc));
            auto ins = [&](int x) {
                ++tc[sum[f[x - 1]][sta]];
            };
            ins(l);
            while (r <= n) {
                while (l < r && c[a[l]] != d[a[l]]) --c[a[l]], ++l, ins(l);
                res += tc[f[r]], ++r;
                if (r <= n) ++c[a[r]];
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}