#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;
vector<int> prefix[9];  // 存储每个数字的出现位置
unordered_map<int, bool> state_cache;  // 缓存常见状态组合

// 使用位运算优化状态转移
inline int get_state(int t1, int t2, int t3, int t4, int t5, int t6, int t7, int t8) {
    int idx = 0;
    idx += w[1]*t1 + w[2]*t2 + w[3]*t3 + w[4]*t4;
    idx += w[5]*t5 + w[6]*t6 + w[7]*t7 + w[8]*t8;
    return idx;
}

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 = get_state(c[1], c[2], c[3], c[4], c[5], c[6], c[7], c[8]);
        ok[idx] = 1;
        state_cache[idx] = true;
    }
}

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();
}

inline int get_count(const vector<int>& pos, int l, int r) {
    return upper_bound(pos.begin(), pos.end(), r) - 
           lower_bound(pos.begin(), pos.end(), l);
}

void solve() {
    int n;
    cin >> n;
    
    // 清空前缀数组
    for(int i = 1; i <= 8; i++) {
        prefix[i].clear();
    }
    
    // 读入数据并构建前缀数组
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix[a[i]].push_back(i);
    }
    
    int ans = 0;
    // 枚举所有可能的长度为3的倍数的区间
    for(int len = 3; len <= n; len += 3) {
        for(int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            
            // 使用二分查找计算区间内每个数字的出现次数
            vector<int> cnt(9);
            for(int k = 1; k <= 8; k++) {
                cnt[k] = get_count(prefix[k], i, j);
            }
            
            // 处理每个计数,应用相同的模运算规则
            int t1 = cnt[1]; if(t1>=3) t1%=3;
            int t2 = cnt[2]; if(t2>=5) t2=(t2-2)%3+2;
            int t3 = cnt[3]; if(t3>=7) t3=(t3-4)%3+4;
            int t4 = cnt[4]; if(t4>=7) t4=(t4-4)%3+4;
            int t5 = cnt[5]; if(t5>=7) t5=(t5-4)%3+4;
            int t6 = cnt[6]; if(t6>=7) t6=(t6-4)%3+4;
            int t7 = cnt[7]; if(t7>=5) t7=(t7-2)%3+2;
            int t8 = cnt[8]; if(t8>=3) t8%=3;
            
            // 计算状态并查找是否合法
            int state = get_state(t1, t2, t3, t4, t5, t6, t7, t8);
            ans += ok[state];
        }
    }
    
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    
    // 预处理所有可能的状态
    init();
    
    while(T--) {
        solve();
    }
    
    return 0;
}