#pragma GCC optimize("O3,unroll-loops")

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long

const int p3[] {1,3,9,27,81,243,729};
const int mxn = 1e5+5;

inline int f(int m, int i) {return (m/p3[i])%3;}

vector<array<int,8>> ok;

void gen_mk() {
	for (int mk=0; mk<p3[6]; mk++) {
		array<int,8> av = {0,0,0,0,0,0,0,0};
		for (int i=0; i<6; i++) {
			int v = f(mk,i);
			av[i] += v;
			av[i+1] += v;
			av[i+2] += v;
		}
		ok.push_back(av);
	}
}

int n,a[mxn],c[8],cnt;

void solve1() {
	for (int i=0; i<n; i++) {
		memset(c,0,sizeof(c));
		for (int j=i+2; j<n; j+=3) {
			c[a[j-2]]++;
			c[a[j-1]]++;
			c[a[j-0]]++;
			for (auto aa : ok) {
				int ok = 1;
				for (int k=0; k<8; k++) {
					if (aa[k] > c[k] || (aa[k]-c[k])%3!=0) {
						ok = 0; break;
					}
				}
				if (ok) {
					cnt++;
					break;
				}
			}
		}
	}
	cout<<cnt<<"\n";
}

int n0,n1,n2;
int amt[3][3][3];

void solve2() {
	memset(amt,0,sizeof(amt));
	n0 = n1 = n2 = 0;
	amt[0][0][0]++;
	for (int i=0; i<n; i++) {
		if (a[i]==0) n0++; n0 %= 3;
		if (a[i]==1) n1++; n1 %= 3;
		if (a[i]==2) n2++; n2 %= 3;
		for (int s=0; s<3; s++) {
			int a0=(n0+s)%3;
			int a1=(n1+s)%3;
			int a2=(n2+s)%3;
			cnt+=amt[a0][a1][a2];
		}
		amt[n0][n1][n2]++;
	}
	cout<<cnt<<"\n";
}

void solve() {
	cin>>n; cnt = 0;
	for (int i=0; i<n; i++) {cin>>a[i]; --a[i];}
	if (n <= 1e3) solve1();
	else solve2();
	
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	gen_mk();
	int t; cin>>t;
	while (t--) solve();
}