#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;

int typeDiff[729][729] = {};
int typeTh[729][8] = {};
vector<int> typeQue[729];
int typePtr[729] = {};

long long solve(vector<vector<int>> block){
    if(block.empty()) return 0;
    //cout << " ----- " << endl;
    //for(auto& b : block){
    //    for(auto a : b) cout << a << " ";
    //    cout << endl;
    //}
    //cout << " ----- " << endl;

    int N = block.size();
    vector<int> typeEx;
    for(auto& a : block) typeEx.push_back(a[8]);
    sort(typeEx.begin(), typeEx.end());
    typeEx.erase(unique(typeEx.begin(), typeEx.end()), typeEx.end());
    //for(int i=N-1; i>=0; i--) typeQue[block[i][8]].push_back(i);
    rep(i,N) typeQue[block[i][8]].push_back(i);
    //for(int t : typeEx) typePtr[t] = typeQue[t].size();
    rep(t,729) typePtr[t] = 0;

    i64 ans = 0;

    for(int l=0; l<N; l++){
        //cout << " l = " << l << endl;
        for(int t : typeEx){
            int v = typeDiff[block[l][8]][t];
            while(typePtr[v] < N){
                //int r = typeQue[t][typePtr[t]-1];
                int r = typePtr[v];
                if(r <= l){ typePtr[v]++; continue; }
                //cout << " th = "; rep(a,8){ cout << typeTh[v][a] << " "; } cout << endl;
                bool ok = true;
                rep(a,8) if(typeTh[v][a] > block[r][a] - block[l][a]) ok = false;
                if(ok) break;
                //typePtr[t]--;
                typePtr[v]++;
            }
            //cout << "s = " << block[l][8] <<  " , t = " << t << " , v = " << v << " , #r = " << typePtr[v] << endl;
            //ans += typePtr[t];
            //cout << "   #r = " << (typeQue[t].end() - lower_bound(typeQue[t].begin(), typeQue[t].end(), typePtr[v])) << endl;
            ans += typeQue[t].end() - lower_bound(typeQue[t].begin(), typeQue[t].end(), typePtr[v]);
        }
    }

    for(int x : typeEx){ typeQue[x].clear(); }
    return ans;
}

i64 fast(vector<int> A){
    int N = A.size();
    vector<vector<vector<int>>> blocks(27); {
        vector<int> C(9);
        vector<int> D(9);
        int a = 0, b = 0, c = 0;
        blocks[0].push_back(D);
        rep(i,N){
            int x = A[i];
            if(x%3 == 1){ a += 1; b += 2; }
            if(x%3 == 2){ b += 1; c += 2; }
            if(x%3 == 0){ c += 1; a += 2; }
            a %= 3; b %= 3; c %= 3;
            C[x] += 2; C[x] %= 3;
            C[x-1] += 1; C[x-1] %= 3;
            D[x-1] += 1;
            int ty = 0;
            for(int k=5; k>=0; k--) ty = ty * 3 + C[k];
            D[8] = ty;
            blocks[a*9+b*3+c].push_back(D);
        }
    }
    i64 ans = 0;
    for(auto& block : blocks) ans += solve(move(block));
    return ans;
}

void testcase(){
    int N; cin >> N;
    vector<int> A(N); rep(i,N) cin >> A[i];
    cout << fast(move(A)) << "\n";
}

bool judge(vector<int> A){
    vector<int> C(8);
    for(auto a : A) C[a-1] += 1;
    rep(k,6) while(C[k] % 3) rep(f,3) C[k+f]--;
    rep(t,8) if(C[t] < 0) return false;
    for(int k=6; k<7; k++) if(C[k] % 3 != 0) return false;
    return true;
}

i64 naive(vector<int> A){
    i64 ans = 0;
    rep(i,A.size()) rep(j,A.size()+1) if(i < j && (j-i)%3 == 0){
        if(judge(vector<int>(A.begin()+i, A.begin()+j))) ans++;
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    {
        int base = 1;
        rep(k,6){
            rep(a,3) rep(b,3) if(a != 0 || b != 0){
                int c = (a+b)%3;
                rep(f,base) rep(g,base) typeDiff[f+a*base][g+c*base] = typeDiff[f][g]+b*base;
            }
            base *= 3;
        }
    }
    rep(i,729){
        vector<int> T(9);
        for(int a=i, b=0; b<6; b++){ T[b]=a%3; a/=3; }
        for(int t=5; t>=0; t--) T[t+3] = (T[t+3] + T[t]) % 3;
        rep(t,6) rep(k,3) typeTh[i][t+k] += T[t];
    }
    int T; cin >> T;
    rep(t,T) testcase();
    return 0;
}