#include<stdio.h>
#include<algorithm>
typedef long long ll;
constexpr int N{100000},L{8},C{729};
constexpr int del[3]{1,1,-2};
int cnt[C+5][L];
int ptr[C+5],vcc[C+5][L],val[C+5],ccc[C+5][(1<<(L<<1))+5];
void init() {
    int tot{0};
    for(int i=0;i!=1<<(L-2<<1);i++) {
        if([&]()->bool {
            for(int j=0;j!=L-2;j++) {
                if((i>>(j<<1)&3)>=3) {
                    return true;
                }
            }
            return false;
        }()) {
            continue;
        }
        ++tot;
        std::fill(cnt[tot],cnt[tot]+L,0);
        for(int j=0;j!=L-2;j++) {
            int c{i>>(j<<1)&3};
            cnt[tot][j]+=c;
            cnt[tot][j+1]+=c;
            cnt[tot][j+2]+=c;
        }
    }
    for(int i=1;i<=C;i++) {
        std::fill(ccc[i],ccc[i]+(1<<(L<<1)),0);
    }
}
int a[N+5],c[N+5][L],v[N+5];
void solve() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",a+i),--a[i];
    }
    ll ans{0};
    std::fill(c[0],c[0]+L,0);
    std::fill(ptr+1,ptr+C+1,0);
    for(int i=1;i<=C;i++) {
        val[i]=0;
        for(int j=0;j!=L;j++) {
            vcc[i][j]=(3-cnt[i][j]%3)%3;
            val[i]|=vcc[i][j]<<(j<<1);
        }
    }
    for(int i=1;i<=n;i++) {
        std::copy(c[i-1],c[i-1]+L,c[i]);
        v[i]=v[i-1]+(del[c[i][a[i]]++%3]<<(a[i]<<1));
        for(int j=1;j<=C;j++) {
            while(ptr[j]<i&&(ptr[j]==0?[&]()->bool {
                for(int p=0;p!=L;p++) {
                    if(c[i][p]-c[ptr[j]][p]<cnt[j][p]) {
                        return false;
                    }
                }
                return true;
            }():c[i][a[ptr[j]]]-c[ptr[j]][a[ptr[j]]]-1>=cnt[j][a[ptr[j]]])) {
                ++ccc[j][v[ptr[j]++]];
            }
            val[j]+=del[vcc[j][a[i]]++%3]<<(a[i]<<1);
            ans+=ccc[j][val[j]];
        }
    }
    for(int i=1;i<=C;i++) {
        for(int j=0;j<=n;j++) {
            ccc[i][v[j]]=0;
        }
    }
    printf("%lld\n",ans);
}
int main() {
    init();
    int t;
    scanf("%d",&t);
    while(t--) {
        solve();
    }
    return 0;
}