#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
typedef long long ll;
typedef pair<ll,ll> PII;
int n,m,k;
ll a[N],b[N],c[N],dep[N];
// char s[N];
int tr[N][26];
int s[N];
int idx=0;
ll ans;
set<int> able;

int now[10],now2[10];

void dfs(int x){
    if(x==8){
        int state=0;
        for(int i=7;i>=0;i--) state=state*3+b[i];
        for(int i=0;i<8;i++) c[i]=b[i];
        for(int i = 0 ; i < 8 ; i ++)
        {
            if(c[i] < 0) return; 
                a[i] %= 3 ;
            if(c[i] > 0)
            {
                if(i + 2 >= 8)  return;
                c[i + 1] -= c[i] ;
                c[i + 2] -= c[i] ;
            }
        }
        
        // cout<<state<<endl;
        able.insert(state);
    }else{
        for(int i=0;i<3;i++){
            b[x]=i;
            dfs(x+1);

        }
    }
}

void __(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i]--;
    }
    s[0]=0;
    memset(now,0,sizeof now);
    for(int i=1;i<=n;i++){
        now[a[i]]++;
        now[a[i]]%=3;
        s[i]=0;
        for(int j=7;j>=0;j--){
            s[i]=s[i]*3+now[j];
        }
        // cout<<s[i]<<" ";
    }
    // cout<<endl;
    ll ans=0;
    map<int,int> mp;
    mp[s[n]]=1;
    for(int i=n-1;i>=0;i--){
        int t=s[i];
        for(int k=0;k<8;k++){
            now[k]=t%3;
            t/=3;
        }
        for(auto j:able){
            int jj=j;
            for(int k=0;k<8;k++){
                now2[k]=j%3;
                j/=3;
                
            }
            // for(int k=0;k<8;k++){
            //     now[k]=(now[k]+now2[k])%3;
            // }
            int res=0;
            for(int k=7;k>=0;k--){
                res=res*3+(now[k]+now2[k])%3;
            }
            if(mp.count(res)){
                // cout<<s[i]<<" "<<jj<<" "<<res<<" "<<mp[res]<<endl;
                ans+=mp[res];
            }
        }
        mp[s[i]]++;
    }
    printf("%lld\n",ans);
}
//2*1 1*2
//2 2 2

int main(){
    
    dfs(0);
    // cout<<able.size()<<endl;
    int _=1;
    cin>>_;
    while(_--){
        __();
    }
}