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