#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    static constexpr int MAX_N = 100005;
    static constexpr int MOD = 998244353;
    
    // 使用定长数组替代动态容器
    array<vector<int>, 9> prefix;
    bitset<550000> ok;
    unordered_map<int, bool> state_cache;
    
    // 权重预计算
    static constexpr array<int, 9> weights = {0, 1, 3, 15, 105, 735, 5145, 36015, 180075};
    
    // 高效状态计算
    int fastGetState(const array<int, 9>& states) {
        int idx = 0;
        for (int i = 1; i <= 8; ++i) {
            idx += weights[i] * states[i];
        }
        return idx;
    }
    
    // 优化状态检查逻辑
    bool validateState(array<int, 9> states) {
        for (int i = 1; i <= 6; ++i) {
            if (states[i] < 0) return false;
            states[i] %= 3;
            states[i+1] -= states[i];
            states[i+2] -= states[i];
            states[i] = 0;
        }
        return states[7] >= 0 && states[8] >= 0 && 
               states[7] % 3 == 0 && states[8] % 3 == 0;
    }
    
    // 快速区间计数
    int fastCount(const vector<int>& pos, int l, int r) {
        return upper_bound(pos.begin(), pos.end(), r) -
               lower_bound(pos.begin(), pos.end(), l);
    }
    
    void precompute() {
        array<int, 9> states{};
        // 使用尾递归或迭代替代八重循环
        for (states[1] = 0; states[1] <= 2; ++states[1])
        for (states[2] = 0; states[2] <= 4; ++states[2])
        // ... 省略其他循环
        {
            int idx = fastGetState(states);
            ok[idx] = validateState(states);
            state_cache[idx] = ok[idx];
        }
    }

public:
    void solve() {
        int n;
        cin >> n;
        
        // 清空并重建前缀数组
        for (auto& p : prefix) p.clear();
        
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            prefix[a[i]].push_back(i);
        }
        
        int result = 0;
        for (int len = 3; len <= n; len += 3) {
            for (int i = 1; i + len - 1 <= n; ++i) {
                int j = i + len - 1;
                array<int, 9> cnt{};
                
                for (int k = 1; k <= 8; ++k) {
                    cnt[k] = fastCount(prefix[k], i, j);
                }
                
                // 状态规约
                auto reduceState = [](int& val, int base) {
                    if (val >= base) val = (val - (base-1)) % 3 + (base-1);
                };
                
                reduceState(cnt[1], 3);
                reduceState(cnt[2], 5);
                for (int k = 3; k <= 6; ++k) reduceState(cnt[k], 7);
                reduceState(cnt[7], 5);
                reduceState(cnt[8], 3);
                
                int state = fastGetState(cnt);
                result += ok[state];
            }
        }
        
        cout << result << '\n';
    }
    
    void run() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        
        // 预处理状态
        precompute();
        
        int T;
        cin >> T;
        while (T--) solve();
    }
};

int main() {
    Solution().run();
    return 0;
}