#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int mod=998244353;
const int N=1e5+5;

int T,n;
int s[8];
LL f[3][3][3][3][3][3][3][3];

int main(){
	scanf("%d",&T);
	while(T--){
		memset(s,0,sizeof s);
		memset(f,0,sizeof f);
		f[0][0][0][0][0][0][0][0]=1;
		scanf("%d",&n);
		LL ans=0;
		for(int i=0,a;i<n;++i){
			scanf("%d",&a);
			++s[--a];
			for(int a0=0;a0<3&&a0<=s[0];++a0)
			for(int a1=0;a1<3&&a0+a1<=s[1];++a1)
			for(int a2=0;a2<3&&a0+a1+a2<=s[2];++a2)
			for(int a3=0;a3<3&&a1+a2+a3<=s[3];++a3)
			for(int a4=0;a4<3&&a2+a3+a4<=s[4];++a4)
			for(int a5=0;a5<3&&a3+a4+a5<=s[5]&&a4+a5<=s[6]&&a5<=s[7];++a5)
				ans+=f[(s[0]-a0)%3]
					[(s[1]-a0-a1)%3]
					[(s[2]-a0-a1-a2)%3]
					[(s[3]-a1-a2-a3)%3]
					[(s[4]-a2-a3-a4)%3]
					[(s[5]-a3-a4-a5)%3]
					[(s[6]-a4-a5)%3]
					[(s[7]-a5)%3];
			++f[s[0]%3][s[1]%3][s[2]%3][s[3]%3][s[4]%3][s[5]%3][s[6]%3][s[7]%3];
		}
		printf("%lld\n",ans);
	}
	
	return 0;
}