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)
dCA9IGludChpbnB1dCgpKQpmb3IgXyBpbiByYW5nZSh0KToKICAgIGNudD0wCiAgICBuID0gaW50KGlucHV0KCkpCiAgICBscyA9IGxpc3QobWFwKGludCxpbnB1dCgpLnNwbGl0KCcgJykpKQogICAgZm9yIGkgaW4gcmFuZ2UoMCxuKToKICAgICAgICBwcm89MQogICAgICAgIGZvciBqIGluIHJhbmdlKGksbik6CiAgICAgICAgICAgIHBybyA9IHBybypsc1tqXQogICAgICAgICAgICBpZihwcm8lNCAhPTIpOgogICAgICAgICAgICAgICAgY250Kz0xCiAgICBwcmludChjbnQp