#include<bits/stdc++.h>
using namespace std;
constexpr int N=100005,C=8;
int n;
int a[N];
int sum[6561];
int cur[C+1];
int cnt[C+1];
long long ans;
void dfs(int step,int val)
{
    if(step>C-2)
    {
        val=val*3+cur[step]%3,step++;
        val=val*3+cur[step]%3,step++;
        ans+=sum[val];
        return;
    }
    for(int c=0;c<=2;c++)
    {
        cnt[step]+=c;
        cnt[step+1]+=c;
        cnt[step+2]+=c;
        if(cnt[step]<=cur[step]&&cnt[step+1]<=cur[step+1]&&cnt[step+2]<=cur[step+2]) dfs(step+1,val*3+(cur[step]-cnt[step])%3);
        cnt[step]-=c;
        cnt[step+1]-=c;
        cnt[step+2]-=c;
    }

    return;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    memset(cur,0,sizeof(cur));
    memset(sum,0,sizeof(sum));
    sum[0]=1;
    ans=0;
    for(int i=1;i<=n;i++)
    {
        cur[a[i]]++;
        dfs(1,0);
        int val=0;
        for(int j=1;j<=C;j++)
            val=val*3+cur[j]%3;
        sum[val]++;
    }
    cout<<ans<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}