#include<iostream>
#include<cstring>
#include<vector>
#include<array>
#include<unordered_map>
using namespace std;
using LL = long long;
int pos[7000];

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int pow3[10];
    pow3[0] = 1;
    for(int i = 1; i < 10; i++) pow3[i] = pow3[i - 1] * 3;

    vector<pair<array<int, 8>, int> > state;

    array<int, 8> cnt{};

    auto dfs = [&](auto &&dfs, int u){
        if (u == 6){
            int val = 0;
            for(int i = 0; i < 8; i++){
                val += pow3[i] * cnt[i];
            }
            state.push_back({cnt, val});
            return;
        }
        for(int i = 0; i < 3; i++){
            cnt[u] += i;
            cnt[u + 1] += i;
            cnt[u + 2] += i;
            dfs(dfs, u + 1);
            cnt[u] -= i;
            cnt[u + 1] -= i;
            cnt[u + 2] -= i;
        }
    };

    dfs(dfs, 0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> v(n + 1);
        vector<array<int, 8> > pre(n + 1);
        int cnt[8]{};
        int val = 0;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            x--;
            a[i] = x;
            val -= cnt[x] * pow3[x];
            cnt[x] = (cnt[x] + 1) % 3;
            val += cnt[x] * pow3[x];
            v[i] = val;
            pre[i] = pre[i - 1];
            pre[i][x] += 1;
        }
        LL ans = 0;
        for(auto &[c, delta] : state){
            int pt = 0;

            int need = 0;
            for(int i = 0; i < 8; i++){
                int k = (3 - c[i] % 3) % 3;
                need += pow3[i] * k;
            }

            for(int i = 1; i <= n; i++){

                int cur = (need % pow3[a[i] + 1]) / pow3[a[i]];
                need -= cur * pow3[a[i]];
                cur = (cur + 1) % 3;
                need += cur * pow3[a[i]];

                auto check = [&](){
                    for(int j = 0; j < 8; j++){
                        if (pre[i][j] - pre[pt][j] < c[j]){
                            return false;
                        }
                    }
                    return true;
                };

                while(check()){
                    pos[v[pt]] += 1;
                    pt++;
                }
                ans += pos[need];
            }
            for(int i = 0; i <= n; i++) pos[v[i]] = 0;
        }
        cout << ans - n << '\n';
    }

}