#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define N 100005
#define MOD 998244353
using namespace std;

int c[9];
int b[9];
int w[9] = {0, 1, 3, 15, 105, 735, 5145, 36015, 180075};
bitset<550000> ok;

void check() {
    memcpy(b,c,sizeof(b));
    for(int i=1;i<=6;++i) {
        if(b[i] < 0) return;
        b[i]%=3;
        b[i+1]-=b[i];
        b[i+2]-=b[i];
        b[i]=0;
    }
    if(b[7]>=0 && b[8]>=0 && b[7]%3==0 && b[8]%3==0) {
        int idx = 0;
        for(int i=1;i<=8;++i) idx += w[i]*c[i];
        ok[idx] = 1;
    }
}

void init() {
    for(c[1]=0;c[1]<=2;++c[1])
        for(c[2]=0;c[2]<=4;++c[2])
            for(c[3]=0;c[3]<=6;++c[3])
                for(c[4]=0;c[4]<=6;++c[4])
                    for(c[5]=0;c[5]<=6;++c[5])
                        for(c[6]=0;c[6]<=6;++c[6])
                            for(c[7]=0;c[7]<=4;++c[7])
                                for(c[8]=0;c[8]<=2;++c[8])
                                    check();
}

int n, a[N], sum[N][9];

inline int get_state(int t1, int t2, int t3, int t4, int t5, int t6, int t7, int t8) {
    return w[1]*t1 + w[2]*t2 + w[3]*t3 + w[4]*t4 
         + w[5]*t5 + w[6]*t6 + w[7]*t7 + w[8]*t8;
}

void solve() {
    cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>a[i];
        for(int j=1;j<=8;++j) sum[i][j] = sum[i-1][j];
        ++sum[i][a[i]];
    }
    
    int ans = 0;
    for(int i=1;i<=n;++i) {
        for(int j=i+2;j<=n;j+=3) {
            int t1 = sum[j][1]-sum[i-1][1]; if(t1>=3) t1%=3;
            int t2 = sum[j][2]-sum[i-1][2]; if(t2>=5) t2=(t2-2)%3+2;
            int t3 = sum[j][3]-sum[i-1][3]; if(t3>=7) t3=(t3-4)%3+4;
            int t4 = sum[j][4]-sum[i-1][4]; if(t4>=7) t4=(t4-4)%3+4;
            int t5 = sum[j][5]-sum[i-1][5]; if(t5>=7) t5=(t5-4)%3+4;
            int t6 = sum[j][6]-sum[i-1][6]; if(t6>=7) t6=(t6-4)%3+4;
            int t7 = sum[j][7]-sum[i-1][7]; if(t7>=5) t7=(t7-2)%3+2;
            int t8 = sum[j][8]-sum[i-1][8]; if(t8>=3) t8%=3;
            
            ans += ok[get_state(t1,t2,t3,t4,t5,t6,t7,t8)];
        }
    }
    cout<<ans<<'\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin>>T;
    init();
    
    while(T--) {
        memset(sum[0], 0, sizeof(sum[0]));  // 每个测试用例前清零
        solve();
    }
    return 0;
}