//Stay Safe :)
#include <bits/stdc++.h>
// video : https://w...content-available-to-author-only...e.com/watch?v=JELQ7dtnChI
using namespace std;
#define lli long long int
int main() {
lli t;
cin>>t;
while(t--){
lli n;
cin>>n;
lli a[n];
for(lli i=0;i<n;i++){
cin>>a[i];
a[i] = a[i]%4;
}
lli cnt=0;
map<lli,pair<lli,lli>> mp;
// from left hand side
for(lli i=0;i<n;i++){
if(a[i]==2 or a[i]==-2){
mp[i].first = cnt;
cnt=0;
}
else{
if(a[i]==0)
cnt=0;
else
cnt++;
}
}
// again initaialize count zero
cnt=0;
//from right hand side
for(lli i=n-1;i>=0;i--){
if(a[i]==2 or a[i]==-2){
mp[i].second = cnt;
cnt=0;
}
else{
if(a[i]==0)
cnt=0;
else
cnt++;
}
}
lli invalid=0;
/*
//uncomment if u want to see all x and y
cout<<"index x y"<<endl;
for(auto xt : mp){
cout<<xt.first<<" "<<xt.second.first<<" "<<xt.second.second<<endl;
}
//uncomment if u want to see all x+1 and y+1
cout<<"index x+1 y+1"<<endl;
for(auto xt : mp){
cout<<xt.first<<" "<<(xt.second.first)+1<<" "<<(xt.second.second)+1<<endl;
}
*/
for(auto xt : mp){
lli x = xt.second.first;
lli y = xt.second.second;
invalid = invalid + (x+1)*(y+1);
}
lli total = n*(n+1)/2;
lli good = total-invalid;
cout<<good<<endl;
}
}
Ly9TdGF5IFNhZmUgOikKCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgovLyB2aWRlbyA6IGh0dHBzOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uZS5jb20vd2F0Y2g/dj1KRUxRN2R0bkNoSQp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGxsaSBsb25nIGxvbmcgaW50IAoKaW50IG1haW4oKSB7CiAgICBsbGkgdDsKICAgIGNpbj4+dDsKICAgIHdoaWxlKHQtLSl7CiAgICAgICAgbGxpIG47CiAgICAgICAgY2luPj5uOwogICAgICAgIGxsaSBhW25dOwogICAgICAgIGZvcihsbGkgaT0wO2k8bjtpKyspewogICAgICAgICAgICBjaW4+PmFbaV07CiAgICAgICAgICAgIGFbaV0gPSBhW2ldJTQ7CiAgICAgICAgfQogICAgICAgIGxsaSBjbnQ9MDsKICAgICAgICBtYXA8bGxpLHBhaXI8bGxpLGxsaT4+IG1wOwogICAgICAgIC8vIGZyb20gbGVmdCBoYW5kIHNpZGUKICAgICAgICBmb3IobGxpIGk9MDtpPG47aSsrKXsKICAgICAgICAgICAgaWYoYVtpXT09MiBvciBhW2ldPT0tMil7CiAgICAgICAgICAgICAgICBtcFtpXS5maXJzdCA9IGNudDsKICAgICAgICAgICAgICAgIGNudD0wOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2V7CiAgICAgICAgICAgICAgICBpZihhW2ldPT0wKQogICAgICAgICAgICAgICAgICAgIGNudD0wOwogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIGNudCsrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAogICAgICAgIC8vIGFnYWluIGluaXRhaWFsaXplIGNvdW50IHplcm8KICAgICAgICBjbnQ9MDsKICAgICAgICAKICAgICAgICAvL2Zyb20gcmlnaHQgaGFuZCBzaWRlCiAgICAgICAgZm9yKGxsaSBpPW4tMTtpPj0wO2ktLSl7CiAgICAgICAgICAgIGlmKGFbaV09PTIgb3IgYVtpXT09LTIpewogICAgICAgICAgICAgICAgbXBbaV0uc2Vjb25kID0gY250OwogICAgICAgICAgICAgICAgY250PTA7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZXsKICAgICAgICAgICAgICAgIGlmKGFbaV09PTApCiAgICAgICAgICAgICAgICAgICAgY250PTA7CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgY250Kys7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgbGxpIGludmFsaWQ9MDsKICAgICAgICAKICAgICAgICAvKgogICAgICAgIAogICAgICAgIC8vdW5jb21tZW50IGlmIHUgd2FudCB0byBzZWUgYWxsIHggYW5kIHkgCgogICAgICAgIGNvdXQ8PCJpbmRleCAgICAgIHggICAgICAgeSI8PGVuZGw7CiAgICAgICAgZm9yKGF1dG8geHQgOiBtcCl7CiAgICAgICAgICAgIGNvdXQ8PHh0LmZpcnN0PDwiICAgICAiPDx4dC5zZWNvbmQuZmlyc3Q8PCIgICAgICAgICAiPDx4dC5zZWNvbmQuc2Vjb25kPDxlbmRsOwogICAgICAgIH0KICAgICAgICAKICAgICAgICAvL3VuY29tbWVudCBpZiB1IHdhbnQgdG8gc2VlIGFsbCB4KzEgYW5kIHkrMSAKICAgICAgICAKICAgICAgICBjb3V0PDwiaW5kZXggICAgICB4KzEgICAgICAgeSsxIjw8ZW5kbDsKICAgICAgICBmb3IoYXV0byB4dCA6IG1wKXsKICAgICAgICAgICAgY291dDw8eHQuZmlyc3Q8PCIgICAgICI8PCh4dC5zZWNvbmQuZmlyc3QpKzE8PCIgICAgICAgICAiPDwoeHQuc2Vjb25kLnNlY29uZCkrMTw8ZW5kbDsKICAgICAgICB9CiAgICAgICAgKi8KICAgICAgICBmb3IoYXV0byB4dCA6IG1wKXsKICAgICAgICAgICAgbGxpIHggPSB4dC5zZWNvbmQuZmlyc3Q7CiAgICAgICAgICAgIGxsaSB5ID0geHQuc2Vjb25kLnNlY29uZDsKICAgICAgICAgICAgaW52YWxpZCA9IGludmFsaWQgKyAoeCsxKSooeSsxKTsKICAgICAgICB9CiAgICAgICAgbGxpIHRvdGFsID0gbioobisxKS8yOwogICAgICAgIGxsaSBnb29kID0gdG90YWwtaW52YWxpZDsKICAgICAgICBjb3V0PDxnb29kPDxlbmRsOwogICAgfQp9