#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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();
}