#pragma GCC optimize("Ofast,inline,unroll-loops")
#include<bits/stdc++.h>
void debug_(const auto&...a){
	((std::cerr<<a<<' '),...)<<'\n';
}
#define debug(A...) debug_(__LINE__,':',#A,'=',A)
using ll=long long;
#define all(s) std::begin(s),std::end(s)
using namespace std;
template<typename T>using V=std::vector<T>;
#define eb emplace_back
#define pb push_back
using pii=std::pair<int,int>;
using Info=int;
constexpr int N=1<<24;
bool val[N];
signed main(){
	auto valid=[&](auto st){
		static int a[8];
		for(int i=0;i<8;++i){
			a[i]=st>>(i*3)&7;
		}
		for(int i=0;i<8;++i){
			if(a[i]<0)return false;
			a[i]%=3;
			if(a[i]){
				if(i+2>=8)return false;
				a[i+1]-=a[i];
				a[i+2]-=a[i];
			}
		}
		return true;
	};
	for(int i=0;i<N;++i){
		val[i]=valid(i);
	}
	cin.tie(0)->sync_with_stdio(0);
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		V<int>a(n);
		// for(int i=0;i<n;++i)a[i]=i%8+1;
		for(auto&x:a)cin>>x,--x;
		using S=std::pair<Info,ll>;
		V<S>f({{0,1}});
		
		ll ans=0;
		for(int i=0;i<n;++i){
			int&x=a[i];
			for(auto&[st,cnt]:f){
				// st[x]++;
				// if(st[x]>=7){
					// st[x]-=3;
				// }
				st+=1<<(x*3);
				if((st>>(x*3)&7)==7){
					st&=~(7<<(x*3));
				}
			}
			f.pb({0,1});
			if(!(i%15)){
				sort(all(f));
				{
					auto first=begin(f),last=end(f);
				 
				    auto result = first;
				    while (++first != last)
				        if (result->first!=first->first){
				        	if(++result != first)*result = std::move(*first);
				        }else{
				        	result->second+=first->second;
				        }
				    f.erase(++result,last);
				}
			}
			for(auto&[st,cnt]:f){
				if(val[st])ans+=cnt;
			}
			// cerr<<ssize(f)<<'\n';
		}
		printf("%lld\n",ans-n);
	}
}