#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

vector<int> a(8);
set<vector<int>> s;

void bt(int i) {
    if (i == 8) {
        s.insert(a);
        return;
    }
    if (i + 3 <= 8) {
        for (int x = 1; x < 3; x++) {
            for (int j = 0; j < 3; j++) {
                a[i + j] += x;
            }
            bt(i + 1);
            for (int j = 0; j < 3; j++) {
                a[i + j] -= x;
            }
        }
    }
    bt(i + 1);
}


struct test {
    void solve() {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            a[i]--;
        }
        vector<int> p3(9);
        p3[0] = 1;
        for (int i = 1; i < 9; i++) p3[i] = p3[i - 1] * 3;
        vector<vector<int>> p(p3[8]);
        vector<int> cc(8);
        for (int i = 0; i < n; i++) {
            cc[a[i]]++;
            int cs = 0;
            for (int j = 0; j < 8; j++) {
                cs += p3[j] * (cc[j] % 3);
            }
            p[cs].push_back(i + 1);
        }

        long res = 0;
        for (auto &c : s) {
            vector<int> b(8);
            int bd = 0;
            for (int i = 0; i < 8; i++) {
                if (b[i] < c[i]) bd++;
            }
            int r = 0;
            auto cc = c;
            for (int i = 0; i < 8; i++) cc[i] %= 3;
            for (int l = 0; l < n; l++) {
                while ((r <= l || bd > 0) && r < n) {
                    int x = a[r++];
                    b[x]++;
                    if (b[x] == c[x]) bd--;
                }

                if (bd > 0) break;
                int cs = 0;
                for (int i = 0; i < 8; i++) {
                    cs += cc[i] * p3[i];
                }

                auto &z = p[cs];
                res += z.size() - (lower_bound(z.begin(), z.end(), r) - z.begin());

                {
                    int x = a[l];
                    b[x]--;
                    if (b[x] == c[x] - 1) bd++;
                }
                cc[a[l]]++;
                cc[a[l]] %= 3;
            }
        }
        cout << res << "\n";
    }
};

int main() {
    ios::sync_with_stdio(false);


    bt(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        test().solve();
    }

    return 0;
}