/*
* Author: sr1jan
* I shall taste the blood...
*
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define mp make_pair
#define pb push_back
typedef long long ll;
// global
// timer code
/* auto start = chrono::high_resolution_clock::now(); */
/* auto end = chrono::high_resolution_clock::now(); */
/* double time_taken = chrono::duration_cast<chrono::nanoseconds>(end - start).count(); */
/* time_taken *= 1e-9; */
/* cout << time_taken << setprecision(9) << endl; */
ll gcd(ll a, ll b) {if(a==0) return b; return gcd(b%a, a);}
bool p_se_sort(pair<int,int> a, pair<int,int> b){
return a.second<b.second;
}
inline bool ss(ll n){
if((n%4)==2||(n%4)==-2) return false;
return true;
}
void solve(){
int n;
cin>>n;
vector<int> a(n);
vector<int> dp(n);
ll c=0;
for(int i=0, ai; i<n; ++i){
cin>>ai;
if(ss(ai)) ++c;
a[i]=ai;
dp[i]=ai%4;
}
int k=2;
while(k<=n){
/* cout << "K: " << k << endl; */
for(int i=0; i<=n-k; i++){
if(dp[i+(k-1)]==0){
++c;
continue;
}
dp[i+(k-1)] = (dp[i+(k-1)] * (a[i]%4)) % 4;
if(ss(dp[i+(k-1)])) ++c;
}
++k;
}
cout << c << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
solve();
}
}
LyogCiAqIEF1dGhvcjogc3IxamFuCiAqIEkgc2hhbGwgdGFzdGUgdGhlIGJsb29kLi4uCiAqCiovCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIHN6KHgpICgoaW50KSh4KS5zaXplKCkpCiNkZWZpbmUgYWxsKHgpICh4KS5iZWdpbigpLCh4KS5lbmQoKQojZGVmaW5lIHJhbGwoeCkgKHgpLnJiZWdpbigpLCh4KS5yZW5kKCkKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBwYiBwdXNoX2JhY2sKCnR5cGVkZWYgbG9uZyBsb25nIGxsOwovLyBnbG9iYWwgCgovLyB0aW1lciBjb2RlCi8qIGF1dG8gc3RhcnQgPSBjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7ICovIAovKiBhdXRvIGVuZCA9IGNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKTsgKi8gCi8qIGRvdWJsZSB0aW1lX3Rha2VuID0gY2hyb25vOjpkdXJhdGlvbl9jYXN0PGNocm9ubzo6bmFub3NlY29uZHM+KGVuZCAtIHN0YXJ0KS5jb3VudCgpOyAqLyAKLyogdGltZV90YWtlbiAqPSAxZS05OyAqLyAKLyogY291dCA8PCB0aW1lX3Rha2VuIDw8IHNldHByZWNpc2lvbig5KSA8PCBlbmRsOyAqLyAKCmxsIGdjZChsbCBhLCBsbCBiKSB7aWYoYT09MCkgcmV0dXJuIGI7IHJldHVybiBnY2QoYiVhLCBhKTt9Cgpib29sIHBfc2Vfc29ydChwYWlyPGludCxpbnQ+IGEsIHBhaXI8aW50LGludD4gYil7CiAgICByZXR1cm4gYS5zZWNvbmQ8Yi5zZWNvbmQ7Cn0KCmlubGluZSBib29sIHNzKGxsIG4pewogICAgaWYoKG4lNCk9PTJ8fChuJTQpPT0tMikgcmV0dXJuIGZhbHNlOwogICAgcmV0dXJuIHRydWU7Cn0KCnZvaWQgc29sdmUoKXsKICAgIGludCBuOwogICAgY2luPj5uOwogICAgdmVjdG9yPGludD4gYShuKTsKICAgIHZlY3RvcjxpbnQ+IGRwKG4pOwogICAgbGwgYz0wOwogICAgZm9yKGludCBpPTAsIGFpOyBpPG47ICsraSl7CiAgICAgICAgY2luPj5haTsKICAgICAgICBpZihzcyhhaSkpICsrYzsKICAgICAgICBhW2ldPWFpOwogICAgICAgIGRwW2ldPWFpJTQ7CiAgICB9CgogICAgaW50IGs9MjsKICAgIHdoaWxlKGs8PW4pewogICAgICAgIC8qIGNvdXQgPDwgIks6ICIgPDwgayA8PCBlbmRsOyAqLwogICAgICAgIGZvcihpbnQgaT0wOyBpPD1uLWs7IGkrKyl7CiAgICAgICAgICAgIGlmKGRwW2krKGstMSldPT0wKXsKICAgICAgICAgICAgICAgICsrYzsKICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGRwW2krKGstMSldID0gKGRwW2krKGstMSldICogKGFbaV0lNCkpICUgNDsKICAgICAgICAgICAgaWYoc3MoZHBbaSsoay0xKV0pKSArK2M7CiAgICAgICAgfQogICAgICAgICsrazsKICAgIH0KICAgIGNvdXQgPDwgYyA8PCAnXG4nOwp9CgppbnQgbWFpbigpewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IAogICAgY2luLnRpZShOVUxMKTsKICAgIGNvdXQudGllKE5VTEwpOwoKICAgIGludCB0OwogICAgY2luPj50OwogICAgd2hpbGUodC0tKXsKICAgICAgICBzb2x2ZSgpOwogICAgfQoKfQo=