#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
const int N = 100005;
int a[N];
int b[9][100005];
int p[9];
int p1[9];

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

    vector<vector<int>> el;
    vector<vector<int>> req;

    for(int i = 0; i < 3*3*3*3*3*3*3*3;i++){
        int x = i;
        vector<int> M(8);
        vector<int> A;
        for(int j = 1; j <= 8; j++){
            M[j-1] = x%3;
            x /= 3;
        }
        A = M;

        for(int j = 1; j <= 6; j++){
            int r = (M[j-1]%3+3)%3;
            M[j-1] -= r;
            M[j]-=r;
            M[j+1]-=r;
        }

        if((M[6]%3+3)%3 == (M[7]%3+3)%3 &&
            (M[5]%3+3)%3 == (M[7]%3+3)%3 ){
                req.push_back(M);
                el.push_back(A);
            }
    }
    int t;
    cin >> t;
    while(t--){
        vector<vector<int>> c(3*3*3*3*3*3*3*3+1);
        int n;
        cin >> n;
        FOR(i,0,n) cin >> a[i];
        for(int i = 1; i <=8;i++) p[i] = 0;
        for(int i = 1; i <= 8;i++){
            for(int j = 0; j < n; j++){
                if(a[j] == i) b[i][p[i]++] = j;
            }
        }
        vector<int> count(9);
        for(int i = 0; i < n; i++){
            count[a[i]]++;
            if(count[a[i]]>=3) count[a[i]]-=3;
            int x = 0;
            int y = 1;
            for(int j = 1; j <= 8; j++){
                x += count[j]*y;
                y*=3;
            }
            c[x].push_back(i);
            
        }
        
        ll ans = 0;
        for(int i = 0; i < el.size();i++){
            vector<int> aux = el[i];
            // if(i == 1) cout <<ans<<'\n';
            bool ok = true;
            for(int j = 1; j <= 8; j++) p1[j] = 0;
            // if(i == 1){
                
            //     for(auto &u: req[i]) cout << u <<" ";
            //     cout <<'\n';
            //     for(auto &u: el[i]) cout << u <<" ";
            //     cout <<'\n';
            // }
            for(int j = 0; j < 8; j++){
                if(req[i][j]  < 0){
                    if(-req[i][j] <= p[j+1]){
                        p1[j+1] = b[j+1][-req[i][j]-1];
                    }else ok = false;
                }else p1[j+1] = -1;
            }
            if(!ok) continue;

            ll mx = 0;
            for(int j = 1; j <= 8; j++) mx = max(mx,(ll)p1[j]);
            for(int j = 0; j < n; j++){
                int ky = 0;
                int y = 1;
                for(int k = 0; k < 8; k++){
                    ky += y*aux[k];
                    y*=3;
                }
                // if(i == 1) cout <<ky<<" ";
                // if(i == 0){
                //     cout <<ky<<" ";
                //     for(auto &u:c[ky]) cout << u <<'\n';
                // }
                if(c[ky].size() > 0){
                    int lo = 0;
                    int hi = (int)c[ky].size()-1;
                    int fn = hi;
                    while(lo <= hi){
                        int mid=(lo+hi)>>1;
                        if(c[ky][mid] >= mx){
                            hi = mid -1;
                            fn = mid;
                        }else lo = mid +1;
                    }
                    if(c[ky][fn] >= mx) ans += (int)c[ky].size()-fn;
                }
                if(p1[a[j]] != -1){
                    p1[a[j]]++;
                    if(p1[a[j]] == p[a[j]]) break;
                }
                mx = max({mx,(ll)p1[a[j]],(ll)j+1});
                aux[a[j]-1]++;
                if(aux[a[j]-1] == 3) aux[a[j]-1] = 0;
                // if(i == 1) cout <<j<<" "<<ans<<'\n';
            }
        }
        cout << ans <<'\n';
    }
}