#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],s[N][10],t[10],h[N][20],z[10],n;
int sum[N];
long long ans;
int cnt,Pow[10];
vector<int>f[N],Ask[N];
void dfs(int i){
	if(i==7){
		cnt++;
		for(int q=1;q<=6;q++){h[cnt][q]+=z[q];h[cnt][q+1]+=z[q];h[cnt][q+2]+=z[q];}
		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();
	dfs(1);
	while(T--){
		ans=0;n=read();
		for(int q=1;q<=n;q++)a[q]=read();
		for(int id=1;id<=cnt;id++){
			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++)t[q]=0;
			int l=0,o=0,opt=0;
			for(int q=1;q<=8;q++)if(h[id][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[id][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[id][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[id][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];
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}