#pragma GCC optimize("O3,unroll-loops")
 
#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <map>
#include <string>
#include <vector>
 
using namespace std;
// int ans = 0;
// map<int, int> masks;
// vector<int> rs;
 
bool check(int n, vector<int> 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;
        now[i] += (3 + (b - now[i] % 3)) % 3;
        // while (now[i] % 3 != b)
        //     now[i]++;
        if (now[i] % 3 < b)
            now[i] += b - now[i] % 3;
    }
    return check(8, now);
}
 
bool mega_check(int mask1, int mask2) {
    vector<int> now(8);
    for (int i = 8 - 1; i >= 0; i -= 1) {
        now[i] += mask1 % 3;
        mask1 /= 3;
        now[i] += 3 * (mask2 % 3);
        mask2 /= 3;
    }
    return check(8, now);
}
 
vector<vector<int>> dp;
 
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, 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) {
        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);
        for (int i : pref_masks)
            ++cnt[i];
 
        int need_mask = 0;
        for (int i = 0; i < m; i += 1) {
            need_mask += ((pref[i] + xd[i]) % 3) * pw3[m - i - 1];
        }
        int mask2 = 0;
        auto change_now = [&](int pos, int d) {
            mask2 -= pw3[m - pos - 1] * min(2, now[pos] / 3);
            now[pos] += d;
            mask2 += pw3[m - pos - 1] * min(2, now[pos] / 3);
        };
        for (int l = 0; l < n; ++l) {
            while (r <= n) {
                if (r > l && dp[mask][mask2]) {
                    break;
                }
                if (r == n) {
                    --cnt[pref_masks[r]];
                    r++;
                    break;
                }
                change_now(a[r], 1);
                --cnt[pref_masks[r]];
                ++r;
            }
            if (r > n)
                break;
 
            answer += cnt[need_mask];
            int i = a[l];
            change_now(i, -1);
            need_mask -= ((pref[i] + xd[i]) % 3) * pw3[m - i - 1];
            ++pref[i];
            need_mask += ((pref[i] + xd[i]) % 3) * pw3[m - i - 1];
        }
 
        while (r <= n) {
            --cnt[pref_masks[r]];
            ++r;
        }
    }
 
    cout << answer << "\n";
}
 
signed main() {
    if (1) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
    }
 
    const int m = 8;
    vector<int> pw3(m + 1, 1);
    for (int i = 1; i <= m; ++i)
        pw3[i] = pw3[i - 1] * 3;
 
    dp.assign(pw3[8], {});
    for (auto mask : good_masks) {
        dp[mask].resize(pw3[8]);
        for (int mask2 = 0; mask2 < pw3[8]; mask2 += 1) {
            dp[mask][mask2] = mega_check(mask, mask2);
        }
    }
    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
 */