#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],e[10],n;
int sum[N];
long long ans;
int cnt,Pow[10],p;
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;
}
bool v[N];
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<=6561;++q){
				sum[q]=0;
				f[q].clear();f[q].push_back(0);	
			}
			for(int q=1;q<=8;q++)t[q]=e[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]];
				e[a[r]]++;
				while(l<r&&opt==8){
					if(e[a[l+1]]>h[id][a[l+1]])e[a[l+1]]--,l++;
					else break;
				}
				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);v[o]=1;
			}
			for(int j=0;j<=8;j++)t[j]=0;
			o=0;int kk=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(int k:Ask[j])ans+=sum[k];
				Ask[j].clear();
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}