#include<bits/stdc++.h>
#define vec vector
using namespace std;
const int N=1e5+10,p3[]={1,3,9,27,81,243,729,2187,6561};
int T,n,a[N],s[N][8],S[N],c[6561];
vec<pair<vec<int>,vec<int>>>g;
inline int get(int x,int y){return x/p3[y]%3;}
inline void init()
{
	for(register int i=0;i<p3[6];i++)
	{
		vec<int>id(8,0);
		for(register int j=0,x=get(i,0);j<6;x=get(i,++j))
			for(int k:{j,j+1,j+2})id[k]+=x;
		vec<int>v(p3[8],0);
		for(register int j=0;j<p3[8];j++)
			for(register int k=0;k<8;k++)v[j]+=(get(j,k)+id[k])%3*p3[k];
		g.push_back({id,v});
	}
}
inline int read()
{
	int s=0,x=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')x=-1;ch=getchar();}
	while(isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*x;
}
signed main()
{
	init();int T=read();
	while(T--)
	{
		n=read();memset(s[0],0,sizeof(s[0]));
		for(register int i=0;i<n;i++)
		{
			a[i]=read();memcpy(s[i+1],s[i],sizeof(s[i]));
			s[i+1][--a[i]]++;
		}
		LL ans=0;
		for(register int i=S[0]=0;i<=n;S[++i]=0)
			for(register int j=0;j<8;j++)S[i]+=s[i][j]%3*p3[j];
		for(auto [u,v]:g)
		{
			int bg=n-1,j=n;
			for(register int x=0;x<8;x++)for(;bg>=0&&s[n][x]-s[bg][x]<u[x];bg--);
			if(bg<0)continue;c[S[n]]++;
			for(register int i=bg;~i;i--)
			{
				while(j>i+1&&s[j][a[j-1]]-s[i][a[j-1]]>u[a[j-1]])c[S[--j]]++;
				ans+=c[v[S[i]]];
			}
			for(;j<=n;j++)c[S[j]]--;
		}
		printf("%d\n",ans);
	}
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:39:17: error: ‘LL’ was not declared in this scope
   39 |                 LL ans=0;
      |                 ^~
answer.code:42:26: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   42 |                 for(auto [u,v]:g)
      |                          ^
answer.code:50:33: error: ‘ans’ was not declared in this scope; did you mean ‘abs’?
   50 |                                 ans+=c[v[S[i]]];
      |                                 ^~~
      |                                 abs
answer.code:54:31: error: ‘ans’ was not declared in this scope; did you mean ‘abs’?
   54 |                 printf("%d\n",ans);
      |                               ^~~
      |                               abs