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

class StateCompressor {
private:
    static constexpr int MOD = 998244353;
    static constexpr int MAX_N = 1000005;
    static constexpr int MAX_STATES = 6666;

    // 预计算的幂
    array<int, 9> powers;
    
    // 状态映射容器
    vector<vector<int>> stateTransitions;
    vector<vector<int>> validStates;

    // 快速读取优化
    int fastRead() {
        char c = getchar();
        int x = 0;
        bool negative = false;
        
        while (!isdigit(c)) {
            negative ^= (c == '-');
            c = getchar();
        }
        
        while (isdigit(c)) {
            x = (x << 1) + (x << 3) + (c ^ 48);
            c = getchar();
        }
        
        return negative ? -x : x;
    }

    // 预处理状态转移
    void preprocessStates() {
        vector<int> currentState(9, 0);
        
        function<void(int)> dfs = [&](int depth) {
            if (depth == 7) {
                int stateKey = computeStateKey(currentState);
                validStates.push_back(currentState);
                return;
            }
            
            for (int i = 0; i <= 2; ++i) {
                for (int j = 0; j <= 2; ++j) {
                    currentState[depth] += i;
                    currentState[depth+1] += i;
                    currentState[depth+2] += i;
                    
                    dfs(depth + 1);
                    
                    currentState[depth] -= i;
                    currentState[depth+1] -= i;
                    currentState[depth+2] -= i;
                }
            }
        };
        
        dfs(1);
    }

    // 计算状态键
    int computeStateKey(const vector<int>& state) {
        int key = 0;
        for (int j = 1; j <= 8; ++j) {
            key = key * 3 + (state[j-1] % 3);
        }
        return key;
    }

    // 构建状态转移矩阵
    void buildStateTransitions() {
        int totalStates = pow(3, 8);
        stateTransitions.resize(totalStates, vector<int>(totalStates, 0));
        
        for (int i = 0; i < totalStates; ++i) {
            for (int j = 0; j < totalStates; ++j) {
                int newState = 0;
                for (int k = 0; k < 8; ++k) {
                    int diff = (i / powers[7-k] % 3) - (j / powers[7-k] % 3) + 3;
                    newState = newState * 3 + (diff % 3);
                }
                stateTransitions[i][j] = newState;
            }
        }
    }

public:
    StateCompressor() {
        // 初始化幂
        powers[0] = 1;
        for (int i = 1; i < 9; ++i) {
            powers[i] = powers[i-1] * 3;
        }
        
        preprocessStates();
        buildStateTransitions();
    }

    // 主要求解函数
    void solve() {
        int n = fastRead();
        vector<int> arr(n + 1);
        vector<vector<int>> prefixCount(n + 1, vector<int>(9, 0));

        // 读取和前缀计数
        for (int i = 1; i <= n; ++i) {
            arr[i] = fastRead();
            prefixCount[i] = prefixCount[i-1];
            prefixCount[i][arr[i]]++;
        }

        long long result = 0;
        vector<int> statePositions(powers[8], n+1);
        
        // 状态处理
        for (int state : validStates) {
            for (int left = 1; left <= n; ++left) {
                vector<int> subsetCount(9, 0);
                for (int k = 1; k <= 8; ++k) {
                    subsetCount[k] = prefixCount[left][k];
                }
                
                // 状态验证和统计
                int validCount = 0;
                int currentPos = left;
                
                while (currentPos <= n) {
                    bool isValid = true;
                    for (int k = 1; k <= 8; ++k) {
                        if (prefixCount[currentPos][k] - prefixCount[left-1][k] < state[k-1]) {
                            isValid = false;
                            break;
                        }
                    }
                    
                    if (!isValid) break;
                    validCount++;
                    currentPos++;
                }
                
                result += validCount;
            }
        }

        cout << result << "\n";
    }

    void run() {
        ios::sync_with_stdio(false);
        cin.tie(0);

        int testCases = fastRead();
        while (testCases--) {
            solve();
        }
    }
};

int main() {
    StateCompressor compressor;
    compressor.run();
    return 0;
}

answer.code: In member function ‘void StateCompressor::solve()’:
answer.code:121:26: error: cannot convert ‘std::vector<int>’ to ‘int’ in initialization
  121 |         for (int state : validStates) {
      |                          ^~~~~~~~~~~
answer.code:135:88: error: invalid types ‘int[int]’ for array subscript
  135 |                         if (prefixCount[currentPos][k] - prefixCount[left-1][k] < state[k-1]) {
      |                                                                                        ^