#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,ans=0,all=0;
int mmp[500005]{};
ll arr[200005]{};
int num[19]{},pw[10]{};
vector<int> pre(9),suf(9),temp(9);
void work()
{
    pw[0]=1;
    for(int i=1;i<=9;i++)
    {
        pw[i]=pw[i-1]*3;
    }
}
void dfs(int depth,int st)
{
    if(depth==7)
    {
       // cout<<st<<' '<<mmp[st]<<'\n';
         ans+=mmp[st];
        return ;
    }
    //cout<<st;
    //cout<<depth<<' ';
    for(int i=0;i<=min({2,pre[depth],pre[depth+1],pre[depth+2]});i++)
    {
        int nst=st;
        if(i)
        {
            if(pre[depth]%3>=i) nst-=i*pw[depth];
            else nst+=(3-i)*pw[depth];
            if(pre[depth+1]%3>=i) nst-=i*pw[depth+1];
            else nst+=(3-i)*pw[depth+1];
            if(pre[depth+2]%3>=i) nst-=i*pw[depth+2];
            else nst+=(3-i)*pw[depth+2];
        }
        //cout<<nst<<'\n';
        pre[depth]-=i,pre[depth+1]-=i,pre[depth+2]-=i;
        dfs(depth+1,nst);
        pre[depth]+=i,pre[depth+1]+=i,pre[depth+2]+=i;
    }
}
void solve() { 
    for(int i=0;i<=50000;i++) mmp[i]=0;
    cin>>n;
    all=0;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    for(int i=0;i<9;i++) pre[i]=0;
    ans=0;
    mmp[0]++;
    int state=0;
    for(int i=1;i<=n;i++)
    {  // cout<<arr[i]<<'a';
        pre[arr[i]]++;
        if(pre[arr[i]]%3==0) state-=2*pw[arr[i]];
        else state+=pw[arr[i]];
        all=state;
        dfs(1,all); 
        mmp[state]++;
    }
    cout<<ans<<'\n';
}
int main() {  
    //ios::sync_with_stdio(false);  
    //cin.tie(0);  
    work();
    int T = 1;  
    cin >> T; 
    while(T--) {  
        solve();  
    }  
    return 0;  
}
/*

*/