#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
int pos[7000];
vector<int> match[7000];

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int pow3[10];
    pow3[0] = 1;
    for(int i = 1; i < 10; i++) pow3[i] = pow3[i - 1] * 3;
    for(int i = 0; i < pow3[8]; i++){
        for(int j = 0; j < pow3[8]; j++){
            int cnt[8];
            bool ok = true;
            for(int k = 0; k < 8; k++){
                int t1 = (i % pow3[k + 1]) / pow3[k];
                int t2 = (j % pow3[k + 1]) / pow3[k];
                cnt[k] = (t1 - t2 + 3) % 3;
            }
            for(int i = 0; i + 2 < 8; i++){
                if (cnt[i] < 0){
                    ok = false;
                    break;
                }
                while(cnt[i] > 0){
                    cnt[i] -= 1;
                    cnt[i + 1] -= 1;
                    cnt[i + 2] -= 1;
                }
            }
            for(int i = 0; i < 8; i++){
                if (cnt[i] != 0){
                    ok = false;
                    break;
                }
            }
            if (ok){
                match[i].push_back(j);
            }
        }
    }

    int T;
    cin >> T;
    while(T--){
        for(int i = 0; i < pow3[8]; i++) pos[i] = 0;
        int n;
        cin >> n;
        int cnt[8]{};
        pos[0] += 1;
        int val = 0;
        LL ans = 0;
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            x--;
            val -= cnt[x] * pow3[x];
            cnt[x] = (cnt[x] + 1) % 3;
            val += cnt[x] * pow3[x];
            for(auto x : match[val]){
                ans += pos[x];
            }
            pos[val] += 1;
        }
        cout << ans << '\n';
    }

}