#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int t,n;
cin >> t;
while(t--)
{
cin >> n;
vector<ll> vi(n);
int x;
for(int i=0;i<n;i++)
{
cin >> x;
x = abs(x);
if(x%2 == 0)
{
if(x%4==0) vi[i] = 2;
else vi[i] = 1;
}
else
{
vi[i] = 0;
}
}
//for(auto& s:vi) cout << s << " ";
ll l=0,r=0;
ll curr=0,ans=0;
bool mrked = false;
// even
while(l<n and r<n)
{
if(l>r)
{
r=l;
mrked = false;
}
if(!mrked) curr += vi[r];
// cout << l << " " << r << " " << curr << endl;
if(curr >=2)
{
ans += n-r;
curr -= vi[l];
l++;
mrked = true;
// cout <<" --- " << l << " " << r << " " << curr << endl;
}
else
{
mrked = false;
r++;
}
}
// cout << ans << endl;
l=0,r=0,curr=0;
while(l<n and r<n)
{
while(vi[l])l++;
if(l >=n )break;
int x=1;
while((l+x < n) and (vi[l+x] == 0)) x++;
ans += (x*(x+1))/2;
l += x;
}
cout << ans << "\n";
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGxsIGxvbmcgbG9uZwoKaW50IG1haW4oKQp7CglpbnQgdCxuOwoJY2luID4+IHQ7CgoJd2hpbGUodC0tKQoJewoJCWNpbiA+PiBuOwoJCXZlY3RvcjxsbD4gdmkobik7CgoJCWludCB4OwoJCWZvcihpbnQgaT0wO2k8bjtpKyspCgkJewoJCQljaW4gPj4geDsKCQkJeCA9IGFicyh4KTsKCQkJCiAgICAgICAgICAgIGlmKHglMiA9PSAwKQoJCQl7ICAKICAgICAgICAgICAgICAgIGlmKHglND09MCkgdmlbaV0gPSAyOwoJCQkJZWxzZSB2aVtpXSA9IDE7CgkJCX0KCQkJZWxzZQoJCQl7CgkJCQl2aVtpXSA9IDA7CgkJCX0KCQl9CgogICAgICAgIC8vZm9yKGF1dG8mIHM6dmkpIGNvdXQgPDwgcyA8PCAiICI7CgoJCWxsIGw9MCxyPTA7CgoJCWxsIGN1cnI9MCxhbnM9MDsKCQlib29sIG1ya2VkID0gZmFsc2U7CgkJLy8gZXZlbgoJCXdoaWxlKGw8biBhbmQgcjxuKQoJCXsKCQkgICAgaWYobD5yKQoJCSAgICB7CgkJICAgICAgICByPWw7CgkJICAgICAgICBtcmtlZCA9IGZhbHNlOwoJCSAgICB9CgkJICAgIAoJCSAgICBpZighbXJrZWQpIGN1cnIgKz0gdmlbcl07CgkJICAvLyAgY291dCA8PCBsIDw8ICIgIiA8PCByIDw8ICIgIiA8PCBjdXJyIDw8IGVuZGw7CgkJICAgIGlmKGN1cnIgPj0yKQoJCSAgICB7CgkJICAgICAgICBhbnMgKz0gbi1yOwoJCSAgICAgICAgY3VyciAtPSB2aVtsXTsKCQkgICAgICAgIGwrKzsKCQkgICAgICAgIG1ya2VkID0gdHJ1ZTsKCQkgICAgICAvLyAgY291dCA8PCIgLS0tICAiIDw8IGwgPDwgIiAiIDw8IHIgPDwgIiAiIDw8IGN1cnIgPDwgZW5kbDsKCQkgICAgICAgIAoJCSAgICB9CgkJICAgIGVsc2UKCQkgICAgewoJCSAgICAgICAgbXJrZWQgPSBmYWxzZTsKCQkgICAgICAgIHIrKzsKCQkgICAgfQoJCX0KCQkKLy8gCQljb3V0IDw8IGFucyA8PCBlbmRsOwoJCWw9MCxyPTAsY3Vycj0wOwoJCXdoaWxlKGw8biBhbmQgcjxuKQoJCXsKCQkgICAgCgkJICAgIHdoaWxlKHZpW2xdKWwrKzsKCQkgICAgCgkJICAgIGlmKGwgPj1uIClicmVhazsKCQkgICAgaW50IHg9MTsKCQkgICAgCgkJICAgIHdoaWxlKChsK3ggPCBuKSBhbmQgKHZpW2wreF0gPT0gMCkpIHgrKzsKCQkgICAgCgkJICAgIGFucyArPSAoeCooeCsxKSkvMjsKCQkgICAgbCArPSB4OwoKCQl9CgkJCgkJY291dCA8PCBhbnMgPDwgIlxuIjsKCX0KfQ==