#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";
	}
}