/*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@         @@@@@@@@@                  @@@@@@@@@         @@@@@@@@@
@@@@@@@@@         @@@@@@@@@                  @@@@@@@@@         @@@@@@@@@
@@@@@@@@@         @@@@@@@@@                  @@@@@@@@@         @@@@@@@@@
@@@@@@@@@         @@@@@@@@@                  @@@@@@@@@         @@@@@@@@@
@@@@@@@@@         @@@@@@@@@                  @@@@@@@@@         @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@         @@@@@@@@@                  @@@@@@@@@         @@@@@@@@@
@@@@@@@@@         @@@@@@@@@                  @@@@@@@@@         @@@@@@@@@
@@@@@@@@@         @@@@@@@@@                  @@@@@@@@@         @@@@@@@@@
@@@@@@@@@         @@@@@@@@@                  @@@@@@@@@         @@@@@@@@@
@@@@@@@@@         @@@@@@@@@                  @@@@@@@@@         @@@@@@@@@
@@@@@@@@@                  @@@@@@@@@@@@@@@@@@                  @@@@@@@@@
@@@@@@@@@                  @@@@@@@@@@@@@@@@@@                  @@@@@@@@@
@@@@@@@@@                  @@@@@@@@@@@@@@@@@@                  @@@@@@@@@
@@@@@@@@@                  @@@@@@@@@@@@@@@@@@                  @@@@@@@@@
@@@@@@@@@                  @@@@@@@@@@@@@@@@@@                  @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@                                                      @@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define maxn 200005
mt19937_64 rng {std::chrono::steady_clock::now().time_since_epoch().count()};
ll mod = 998244353;
ll MOD = 998244353;
//cout<<"panduan\n";
//auto dfs = [&](auto &self,int x,int f)->void{self(self,x,f);};




void solve(){
	
	int n = 0;
	cin>>n;
	vector<int>arr(n);
	vector<vector<int>>pre(n+1,vector<int>(8));
	vector<int>temp(729);
	for(int i = 0;i<n;i++){
		cin>>arr[i];
		arr[i]--;
		pre[i+1][arr[i]]++;
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<8;j++){
			pre[i][j]+=pre[i-1][j];
		}
	}
	int all[7] = {0};
	//all[0] = 1;
	ll ans = 0;
	for(int i = 0;i<729;i++){
	//int i = 1;	
		int num[8] = {0};
		vector<int>cnt(6561);
		for(int j = 0;j<6;j++){
			if(all[j]){
				num[j]+=all[j];
				num[j+1]+=all[j];
				num[j+2]+=all[j];
			}
		}
		int l = 0,r = 0;
		int numl[8] = {0},numr[8] = {0};
		//cnt[0]++;

		for(int j = 0;j<n;j++){
			numr[arr[j]]++;
			r++;
			if(numr[arr[j]]>=3)numr[arr[j]] = 0;
			while(l<r){
				int ok = 1;
				for(int k = 0;k<8;k++){
					if(pre[r][k]-pre[l][k]<num[k]){
						ok = 0;
						break;
					}
				}	
				if(ok){
					int haha = 0,te = 1;
					for(int k = 0;k<8;k++){
						haha+=te*numl[k];
						te*=3;
					}
					cnt[haha]++;
					numl[arr[l]]++;
					if(numl[arr[l]]==3)numl[arr[l]] = 0;
					l++;
					
				}else{
					break;
				}
			}
			
			int haha = 0,te = 1;
			for(int k = 0;k<8;k++){
				haha+=te*((numr[k]-num[k]+6)%3);
				te*=3;
			}
			ans+=cnt[haha];
			//r++;
		}
		
		all[0]++;
		int dex = 0;
		while(dex<=5&&all[dex]>=3){
			all[dex++] = 0;
			all[dex]++;
		}
	}

	cout<<ans<<"\n";

}




int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t = 1;
	cin>>t;
	while(t--){
		solve();
	}

	return 0;
}