#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;
signed main(){
	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}});
		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;
		};
		ll ans=0;
		for(auto&x:a){
			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});
			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(valid(st))ans+=cnt;
			}
			// cerr<<ssize(f)<<'\n';
		}
		printf("%lld\n",ans-n);
	}
}