#include <bits/stdc++.h>  
#define ll long long  
using namespace std;  
const long long mod = 20020219, inf = 1e18;  
ll n, m, k, q,l,r,cnt=0,ans=0;
map<vector<int>,int> mmp;
ll arr[200005]{};
int num[19]{};
vector<int> pre(9),suf(9),temp(9);
void dfs(int depth)
{
    if(depth==7)
    {
        bool tag=true;
        for(int i=1;i<=8;i++)
        {   
            temp[i]=pre[i]-num[i];
            if(temp[i]<0) tag=false;
            temp[i]%=3;       
        }
        if(tag)
        {//for(int i=1;i<=8;i++) cout<<temp[i]<<' ';
           // cout<<mmp[temp]<<'\n';
         ans+=mmp[temp];
        }
        return ;
    }
    for(int i=0;i<=2;i++)
    {
        num[depth]+=i,num[depth+1]+=i,num[depth+2]+=i;
        dfs(depth+1);
        num[depth]-=i,num[depth+1]-=i,num[depth+2]-=i;
    }
}
void solve() { 
    mmp.clear();
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    for(int i=0;i<9;i++) pre[i]=0,suf[i]=0;
    ans=0;
    mmp[pre]++;
    for(int i=1;i<=n;i++)
    {  // cout<<arr[i]<<'a';
        pre[arr[i]]++;
        suf[arr[i]]=pre[arr[i]]%3;
        // for(int i=1;i<10;i++)
        // {
        //     cout<<suf[i]<<' '; 
        // }
       // cout<<'\n';
        dfs(1); 
        mmp[suf]++;
        //cout<<ans<<' ';
    }
    cout<<ans<<'\n';
}
int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(0);  
    //pre();
    int T = 1;  
    cin >> T; 
    while(T--) {  
        solve();  
    }  
    return 0;  
}
/*

*/