#include<bits/stdc++.h>
#define N 1000005
using namespace std;
long long t,n,m,k,flag[N],ans=1,mod=998244353,a[N],cnt,nown,pre[N][10],nub[10],xx[10];
inline long long rd()
{
    long long 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 << 1 ) + ( x << 3 ) + ( ch ^ 48 );
        ch = getchar();
    }
    return x * f;
}

long long det()
{
	xx[1]=nub[1]%3;
	if(nub[2]<xx[1]){return 0;}
	xx[2]=(nub[2]-xx[1])%3;
	for(int j=3;j<=6;j++)
	{
		if(nub[j]-xx[j-2]-xx[j-1]<0)return 0;
		xx[j]=(nub[j]-xx[j-2]-xx[j-1])%3;
	}
	if((nub[7]-xx[5]-xx[6])%3==0&&(nub[8]-xx[6])%3==0)return 1;
	else return 0;
}

int main()
{
//	cin>>n;
//	for(int j=1;j<=n;j++)
//	nub[j]=rd();
//	cout<<det()<<endl;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		n=rd();ans=0;
		for(int j=1;j<=n+1;j++)
		{
			flag[j]=-1;
		}
		for(int j=1;j<=n;j++)
		{
			long long c=rd();
			for(int l=1;l<=8;l++)
			pre[j][l]=pre[j-1][l];
			pre[j][c]++;
		}
		for(int j=1;j<=n-2;j++)
		{
			for(int l=1;l<=8;l++)
			{
				nub[l]=pre[j+2][l]-pre[j-1][l];
			}
			if(det())flag[j]=j+2;
			else flag[j]=-1;
		}
		for(int l=1;l<=8;l++)nub[l]=0;
		nown=n;
		for(int j=n-2;j>=1;j-=3)
		{
			if(flag[j]!=-1)continue;
			for(int l=1;l<=8;l++)
			{
				nub[l]+=pre[j+2][l]-pre[j-1][l];
			}
			if(det())
			{
				flag[j]=nown;nown=j-1;
				for(int l=1;l<=8;l++)nub[l]=0;
			}
		}
		for(int l=1;l<=8;l++)nub[l]=0;
		nown=n-1;
		for(int j=n-3;j>=1;j-=3)
		{
			if(flag[j]!=-1)continue;
			for(int l=1;l<=8;l++)
			{
				nub[l]+=pre[j+2][l]-pre[j-1][l];
			}
			if(det())
			{
				flag[j]=nown;nown=j-1;
				for(int l=1;l<=8;l++)nub[l]=0;
			}
		}
		for(int l=1;l<=8;l++)nub[l]=0;
		nown=n-2;
		for(int j=n-4;j>=1;j-=3)
		{
			if(flag[j]!=-1)continue;
			for(int l=1;l<=8;l++)
			{
				nub[l]+=pre[j+2][l]-pre[j-1][l];
			}
			if(det())
			{
				flag[j]=nown;nown=j-1;
				for(int l=1;l<=8;l++)nub[l]=0;
			}
		}
//		long long bg=0;
		cnt=0;
		for(int j=1;j<=n+1;)
		{
			if(flag[j]==-1)
			{
				ans+=cnt*(cnt+1)/2;
				cnt=0;j+=3;
			}
			else
			{
				cnt++;
				j=flag[j]+1;
			}
		}
		cnt=0;
		for(int j=2;j<=n+1;)
		{
			if(flag[j]==-1)
			{
				ans+=cnt*(cnt+1)/2;
				cnt=0;j+=3;
			}
			else
			{
				cnt++;
				j=flag[j]+1;
			}
		}
		cnt=0;
		for(int j=3;j<=n+1;)
		{
			if(flag[j]==-1)
			{
				ans+=cnt*(cnt+1)/2;
				cnt=0;j+=3;
			}
			else
			{
				cnt++;
				j=flag[j]+1;
			}
		}
//		for(int j=1;j<=n-2;j++)
//		{
//			cout<<flag[j]<<" ";
//		}
//		cout<<endl;
		cout<<ans<<endl;
		
	}
}