#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],s[N][10],t[10],h[N],z[10],n;
int sum[N];
long long ans;
int check(int i,int j){
	for(int q=1;q<=8;q++)if(s[j][q]-s[i][q]<h[q])return 0;
	return 1;
}
int p,Pow[10];
vector<int>f[N],Ask[N];
void dfs(int i){
	if(i==7){
		p++;
		for(int q=0;q<=n;q++)Ask[q].clear();
		for(int q=0;q<=8000;q++)f[q].clear(),f[q].push_back(0),sum[q]=0;
		for(int q=1;q<=8;q++)h[q]=t[q]=0;
		for(int q=1;q<=6;q++){h[q]+=z[q];h[q+1]+=z[q];h[q+2]+=z[q];}
		int l=0,o=0,opt=0;
		for(int q=1;q<=8;q++)if(h[q]==0)opt++;
		for(int r=1;r<=n;r++){
			for(int j=1;j<=8;j++)s[r][j]=s[r-1][j];
			s[r][a[r]]++;if(s[r][a[r]]==h[a[r]])opt++;
			o=o-t[a[r]]*Pow[8-a[r]];
			t[a[r]]=s[r][a[r]]%3;
			o=o+t[a[r]]*Pow[8-a[r]];
			while(l<r&&opt==8){
				int p=1;
				for(int q=1;q<=8;q++)if(s[r][q]-s[l+1][q]<h[q]){p=0;break;}
				if(p==0)break;
				l++;
			}
			if(opt==8){
				int k=0;for(int i=1;i<=8;i++)k=k*3+(s[r][i]-h[i])%3;
				int j=f[k][upper_bound(f[k].begin(),f[k].end(),l)-f[k].begin()-1];
				Ask[j].push_back(k);
			}
			f[o].push_back(r);
		}
		for(int j=0;j<=8;j++)t[j]=0;
		o=0;
		for(int j=0;j<=n;j++){
			if(j!=0)o-=t[a[j]]*Pow[8-a[j]];
			t[a[j]]=(t[a[j]]+1)%3;
			if(j!=0)o+=t[a[j]]*Pow[8-a[j]];
			sum[o]++;
			for(auto k:Ask[j])ans+=sum[k];
		}
		return ;
	}
	z[i]=0;dfs(i+1);
	z[i]=1;dfs(i+1);
	z[i]=2;dfs(i+1);
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
	return x*f;
}
int main(){
	Pow[0]=1;for(int q=1;q<=8;q++)Pow[q]=Pow[q-1]*3;
	int T;T=read();
	while(T--){
		ans=0;n=read();
		for(int q=1;q<=n;q++)a[q]=read();
		dfs(1);
		cout<<ans<<"\n";
	}
	return 0;
}