#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e5+5,M=729+5,V=6561+5;
int n,T,la[M],cn[15],an[M][15],cnt,su,a[N],ans[9*M],no[M][15],zf[9],da[V][M];
vector<int> b[N];
void dfs(int g){
	if(g==7){
		cnt++;
		for(int i=1;i<=8;i++) an[cnt][i]=cn[i];
		return;
	}
	dfs(g+1);
	for(int i=0;i<3;i++) cn[g+i]++;
	dfs(g+1);
	for(int i=0;i<3;i++) cn[g+i]++;
	dfs(g+1);
	for(int i=0;i<3;i++) cn[g+i]-=2;
}
void dfs1(int g){
	if(g==9){
		int ans=0;
		for(int j=1;j<=8;j++) ans+=zf[j]*cn[j];
		for(int i=1;i<=cnt;i++){
			int ans1=0;
			for(int j=1;j<=8;j++) ans1+=(cn[j]-an[i][j]+3)%3*zf[j];
			da[ans][i]=ans1;
		}
		return;
	}
	dfs1(g+1);
	cn[g]++;
	dfs1(g+1);
	cn[g]++;
	dfs1(g+1);
	cn[g]-=2;
}
int main(){
	memset(cn,0,sizeof(cn));
	zf[1]=1;
	for(int i=2;i<=8;i++) zf[i]=zf[i-1]*3;
	scanf("%d",&T);
	dfs(1);
	dfs1(1);
	while(T--){
		scanf("%d",&n);
		b[0].clear();
		for(int i=1;i<=n;i++){
			b[i].clear();
			scanf("%d",&a[i]);
		}
		for(int i=1;i<=cnt;i++){
			la[i]=1;
			memset(cn,0,sizeof(cn));
			cn[a[1]]=1;
			for(int j=1;j<=8;j++){
				while(cn[j]<an[i][j] && la[i]<=n){
					cn[a[la[i]+1]]++;
					la[i]++;
				}
			}
		}
		int now=0;
		memset(cn,0,sizeof(cn));
		for(int i=1;i<=n;i++){
			now-=zf[a[i]]*cn[a[i]];
			cn[a[i]]=(cn[a[i]]+1)%3;
			now+=zf[a[i]]*cn[a[i]];
			for(int j=1;j<=cnt;j++){
				no[j][a[i]]++;
				if(la[j]<=i){
					while(no[j][a[la[j]]]>an[j][a[la[j]]] && la[j]<i){
						no[j][a[la[j]]]--;
						la[j]++;
					}
					b[la[j]-1].push_back(da[now][j]);
				}
			}
		}
		now=0;
		long long ans1=0;
		memset(ans,0,sizeof(ans));
		memset(cn,0,sizeof(cn));
		for(int i=0;i<n;i++){
			now-=zf[a[i]]*cn[a[i]];
			cn[a[i]]=(cn[a[i]]+1)%3;
			now+=zf[a[i]]*cn[a[i]];
			ans[now]++;
			for(int j=0;j<(int)b[i].size();j++) ans1+=ans[b[i][j]];
		}
		printf("%lld\n",ans1);
	}
	return 0;
}