#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+5,M=15,K=1e4+5,S=(1<<8)+5;
int T,n,a[N];
int st[K][9],iscor[K][S],tot,b[10],d[10];
map<vector<int>,int>mp;
void dfs1(int step) {
	if(step==9)
	{
		for(int i=0;i<(1<<8);i++) {
			for(int j=1;j<=8;j++)b[j]=((i>>j-1)&1)*3+a[j];
			for(int i=1;i<=9;i++)d[i]=b[i]-b[i-1];
			if((d[1]+d[4]+d[7])!=0)continue;
			if((d[2]+d[5]+d[8])!=0)continue;
			if((d[3]+d[6]+d[9])!=0)continue;
			if(d[1]<0 || d[2]<0 || d[3]<0 || d[7]>0 || d[8]>0 || d[9]>0)continue;
			vector<int>now(8);
			for(int i=1;i<=8;i++)now[i-1]=a[i];
			if(!mp.count(now)) {
				tot++,mp[now]=tot;
				for(int j=1;j<=8;j++)st[tot][j]=b[j];
			}
			int ns=mp[now];
			iscor[ns][i]=1;
		}
		return ;
	}
	for(int i=0;i<3;i++)a[step]=i,dfs1(step+1);
}
void init() {
	dfs1(1);
	//tot=1;
	for(int i=1;i<=tot;i++)
		for(int j=0;j<8;j++)for(int k=0;k<(1<<8);k++)if((k>>j)&1)iscor[i][k]|=iscor[i][k^(1<<j)];
}
vector<int>pos[K];
int sum[N][9],L[K];
void solve() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=0;i<=1e4;i++)pos[i].clear(),L[i]=n+1;
	for(int i=0;i<=n;i++) {
		if(i>0) {
			for(int j=1;j<=8;j++)sum[i][j]=sum[i-1][j];
			sum[i][a[i]]++;
		}
		vector<int>now(8);int st=0;
		for(int j=1;j<=8;j++)now[j-1]=sum[i][j]%3,st=st*3+now[j-1];
		pos[st].push_back(i);
	}
	ll ans=0;
	//exit(0);
	for(int i=n;i;i--) {
		for(int j=1;j<=tot;j++) {
			while(L[j]>i+1) {
				int S=0;
				for(int k=1;k<=8;k++)S|=(sum[L[j]-1][k]-sum[i-1][k]>=3);
				if(iscor[j][S])L[j]--;else break;
			}
			vector<int>now(8);
			int vv=0;
			for(int k=1;k<=8;k++)now[k-1]=(st[j][k]+sum[i-1][k]+3)%3;
			//cerr<<'\n';
			for(int k=0;k<8;k++)vv=vv*3+now[k];
			//cerr<<'\n';
			auto&c=pos[vv];
			//cerr<<i<<' '<<j<<' '<<L[j]<<' '<<c.size()<<'\n';
			ans+=c.end()-lower_bound(c.begin(),c.end(),L[j]);
			//cerr<<ans<<'\n';
		}
	}cout<<ans<<'\n';
}
int main() {
	#ifndef ONLINE_JUDGE
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	#endif 
	init();
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}