#pragma GCC optimize("O3,unroll-loops")

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>

using namespace std;
//int ans = 0;
//map<int, int> masks;
//vector<int> rs;

bool check(int n, vector<int> a) {
    vector<int> c = a;
    for (int i = 0; i < n; ++i) {
        a[i] %= 3;
        if (i + 2 < n && a[i + 1] >= a[i] && a[i + 2] >= a[i]) {
            a[i + 1] -= a[i];
            a[i + 2] -= a[i];
            a[i] = 0;
        }
        if (a[i] > 0) return false;
    }
//    for (int i = 0; i < n; ++i) c[i] %= 3;
//    int mask = 0;
//    for (int i: c) mask = mask * 3 + i;
//    if (!masks.count(mask)) {
//        masks[mask] = 1;
//        rs.push_back(mask);
//    }
//    // ans++;
    return true;
}

void gen(int n, vector<int> a) {
    if (n == a.size()) {
        check(n, a);
        return;
    }
    for (int i = 1; i <= 8; ++i) {
        a.push_back(i);
        gen(n, a);
        a.pop_back();
    }
}

inline void solve() {
    int n;
    cin >> n;
    vector<int> a;
    gen(n, a);
//    cout << rs.size();
    // cout << "{";
    // for (int i = 0; i < rs.size(); ++i) {
    //     cout << rs[i];
    //     if (i + 1 < rs.size()) cout << ",";
    // }
    // cout << "}";
}

vector<int> good_masks = {3276, 3289, 3275, 3315, 3301, 3305, 3246, 3250, 3263, 3393, 3379, 3392, 3324, 3337, 3341,
                          3363, 3367, 3353, 3198, 3211, 3188, 3237, 3214, 3227, 3172, 3185, 3159, 3523, 3536, 3510,
                          3549, 3562, 3539, 3507, 3484, 3497, 3627, 3640, 3626, 3585, 3571, 3575, 3597, 3601, 3614,
                          3420, 3406, 3419, 3432, 3445, 3449, 3471, 3475, 3461, 3145, 3158, 3132, 3090, 3103, 3080,
                          3129, 3106, 3119, 2925, 2938, 2924, 2964, 2950, 2954, 2976, 2980, 2993, 3042, 3028, 3041,
                          3054, 3067, 3071, 3012, 3016, 3002, 4251, 4264, 4241, 4290, 4267, 4280, 4225, 4238, 4212,
                          4329, 4342, 4328, 4368, 4354, 4358, 4299, 4303, 4316, 4203, 4189, 4202, 4134, 4147, 4151,
                          4173, 4177, 4163, 3847, 3860, 3834, 3873, 3886, 3863, 3831, 3808, 3821, 3708, 3721, 3707,
                          3666, 3652, 3656, 3678, 3682, 3695, 3744, 3730, 3743, 3756, 3769, 3773, 3795, 3799, 3785,
                          3955, 3968, 3942, 3900, 3913, 3890, 3939, 3916, 3929, 3978, 3991, 3977, 4017, 4003, 4007,
                          4029, 4033, 4046, 4095, 4081, 4094, 4107, 4120, 4124, 4065, 4069, 4055, 2388, 2401, 2378,
                          2427, 2404, 2417, 2362, 2375, 2349, 2223, 2236, 2222, 2262, 2248, 2252, 2193, 2197, 2210,
                          2340, 2326, 2339, 2271, 2284, 2288, 2310, 2314, 2300, 2470, 2483, 2457, 2496, 2509, 2486,
                          2454, 2431, 2444, 2574, 2587, 2573, 2532, 2518, 2522, 2544, 2548, 2561, 2610, 2596, 2609,
                          2622, 2635, 2639, 2661, 2665, 2651, 2821, 2834, 2808, 2766, 2779, 2756, 2805, 2782, 2795,
                          2844, 2857, 2843, 2883, 2869, 2873, 2895, 2899, 2912, 2718, 2704, 2717, 2730, 2743, 2747,
                          2688, 2692, 2678, 6435, 6448, 6434, 6474, 6460, 6464, 6405, 6409, 6422, 6552, 6538, 6551,
                          6483, 6496, 6500, 6522, 6526, 6512, 6357, 6370, 6347, 6396, 6373, 6386, 6331, 6344, 6318,
                          5953, 5966, 5940, 5979, 5992, 5969, 5937, 5914, 5927, 6057, 6070, 6056, 6015, 6001, 6005,
                          6027, 6031, 6044, 5850, 5836, 5849, 5862, 5875, 5879, 5901, 5905, 5891, 6304, 6317, 6291,
                          6249, 6262, 6239, 6288, 6265, 6278, 6084, 6097, 6083, 6123, 6109, 6113, 6135, 6139, 6152,
                          6201, 6187, 6200, 6213, 6226, 6230, 6171, 6175, 6161, 4494, 4507, 4484, 4533, 4510, 4523,
                          4468, 4481, 4455, 4572, 4585, 4571, 4611, 4597, 4601, 4542, 4546, 4559, 4446, 4432, 4445,
                          4377, 4390, 4394, 4416, 4420, 4406, 4819, 4832, 4806, 4845, 4858, 4835, 4803, 4780, 4793,
                          4680, 4693, 4679, 4638, 4624, 4628, 4650, 4654, 4667, 4716, 4702, 4715, 4728, 4741, 4745,
                          4767, 4771, 4757, 4927, 4940, 4914, 4872, 4885, 4862, 4911, 4888, 4901, 4950, 4963, 4949,
                          4989, 4975, 4979, 5001, 5005, 5018, 5067, 5053, 5066, 5079, 5092, 5096, 5037, 5041, 5027,
                          5547, 5560, 5537, 5586, 5563, 5576, 5521, 5534, 5508, 5382, 5395, 5381, 5421, 5407, 5411,
                          5352, 5356, 5369, 5499, 5485, 5498, 5430, 5443, 5447, 5469, 5473, 5459, 5629, 5642, 5616,
                          5655, 5668, 5645, 5613, 5590, 5603, 5733, 5746, 5732, 5691, 5677, 5681, 5703, 5707, 5720,
                          5769, 5755, 5768, 5781, 5794, 5798, 5820, 5824, 5810, 5251, 5264, 5238, 5196, 5209, 5186,
                          5235, 5212, 5225, 5274, 5287, 5273, 5313, 5299, 5303, 5325, 5329, 5342, 5148, 5134, 5147,
                          5160, 5173, 5177, 5118, 5122, 5108, 1092, 1105, 1082, 1131, 1108, 1121, 1066, 1079, 1053,
                          1170, 1183, 1169, 1209, 1195, 1199, 1140, 1144, 1157, 1044, 1030, 1043, 975, 988, 992, 1014,
                          1018, 1004, 1417, 1430, 1404, 1443, 1456, 1433, 1401, 1378, 1391, 1278, 1291, 1277, 1236,
                          1222, 1226, 1248, 1252, 1265, 1314, 1300, 1313, 1326, 1339, 1343, 1365, 1369, 1355, 796, 809,
                          783, 741, 754, 731, 780, 757, 770, 819, 832, 818, 858, 844, 848, 870, 874, 887, 936, 922, 935,
                          948, 961, 965, 906, 910, 896, 2145, 2158, 2135, 2184, 2161, 2174, 2119, 2132, 2106, 1980,
                          1993, 1979, 2019, 2005, 2009, 1950, 1954, 1967, 2097, 2083, 2096, 2028, 2041, 2045, 2067,
                          2071, 2057, 1498, 1511, 1485, 1524, 1537, 1514, 1482, 1459, 1472, 1602, 1615, 1601, 1560,
                          1546, 1550, 1572, 1576, 1589, 1638, 1624, 1637, 1650, 1663, 1667, 1689, 1693, 1679, 1849,
                          1862, 1836, 1794, 1807, 1784, 1833, 1810, 1823, 1872, 1885, 1871, 1911, 1897, 1901, 1923,
                          1927, 1940, 1746, 1732, 1745, 1758, 1771, 1775, 1716, 1720, 1706, 364, 377, 351, 390, 403,
                          380, 348, 325, 338, 468, 481, 467, 426, 412, 416, 438, 442, 455, 261, 247, 260, 273, 286, 290,
                          312, 316, 302, 715, 728, 702, 660, 673, 650, 699, 676, 689, 495, 508, 494, 534, 520, 524, 546,
                          550, 563, 612, 598, 611, 624, 637, 641, 582, 586, 572, 117, 130, 116, 156, 142, 146, 87, 91,
                          104, 234, 220, 233, 165, 178, 182, 204, 208, 194, 39, 52, 29, 78, 55, 68, 13, 26, 0};
const int MAX_MASK = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3;
const int GOOD_SIZE = 729;

inline int to_mask(const vector<int>& now) {
    int mask = 0;
    for (int i: now) mask = mask * 3 + i % 3;
    return mask;
}
#define ll long long

bool check2(vector <int> now, int need_mask) {
    for (int i = 8 - 1; i >= 0; --i) {
        int b = need_mask % 3;
        need_mask /= 3;
        while (now[i] % 3 != b) now[i]++;
//        if (now[i] % 3 < b) now[i] += b - now[i] % 3;
    }
    return check(8, now);
}

void real_solve() {
    sort(good_masks.begin(), good_masks.end());
    int n;
    cin >> n;
    const int m = 8;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        --a[i];
    }
    vector<int> cnt(MAX_MASK);
    vector<int> pw3(m, 1);
    for (int i = 1; i < m; ++i) pw3[i] = pw3[i - 1] * 3;
    vector<int> pref_masks(n + 1);
    {
        vector<int> now(m);
        for (int i = 0; i < n; ++i) {
            ++now[a[i]];
            pref_masks[i + 1] = to_mask(now);
        }
    }

    ll answer = 0;

    for (int mask: good_masks) {
        if (mask == 1 + 3 + 9) {
            int bob = 0;
        }
        vector<int> xd(8);
        int tmask = mask;
        for (int i = m - 1; i >= 0; --i) {
            xd[i] = tmask % 3;
            tmask /= 3;
        }
        int r = 0;
        vector<int> now(m);
        vector <int> pref(m);
        int cur_mask = 0;
        for (int i = 0; i < MAX_MASK; ++i) cnt[i] = 0;
        for (int i: pref_masks) ++cnt[i];

        for (int l = 0; l < n; ++l) {
            while (r <= n) {
                if (r > l && check2(now, mask)) {
                    break;
                }
                if (r == n) {
                    --cnt[pref_masks[r]];
                    r++;
                    break;
                }
                ++now[a[r]];
                --cnt[pref_masks[r]];
                ++r;
            }
            if (r > n) break;

            int need_mask = 0;
            for (int i = 0; i < m; ++i) {
                need_mask += ((pref[i] + xd[i]) % 3) * pw3[m - i - 1];
            }
            answer += cnt[need_mask];
            --now[a[l]];
            ++pref[a[l]];

        }
    }

    cout << answer << "\n";
}

signed main() {
    if (1) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
    }
    // pre_calc();
    int t = 1;
    cin >> t;
    while (t--) {
        real_solve();
    }
    return 0;
}

/*
 5
4
1 1 1 1
6
1 2 3 1 2 3
7
6 5 8 7 6 3 2
8
1 2 1 2 1 2 1 3
9
2 2 4 4 1 1 1 3 3

 1
 7
6 5 8 7 6 3 2
 */