t = int(input())
for _ in range(t):
    n=int(input())
    ls = list(map(int,input().split(' ')))
    cnt=0
    for i in range(0,n):
        pro=1
        for j in range(i,n):
            pro = (pro*ls[j])%4
            if(pro != 2):
                cnt+=1
    print(cnt)