Mahesh Chaudhary likes playing with xor.
now he has n numbers and he wants to find out xor of all possible subsets and
check out how many of them are distinct prime numbers i.e if two subsets have
value 2 we need to count 2 only once

Input
first line contains t denoting number of test cases
next line contains n
and next line contains n numbers whose subset xor is to be found

output
print a number denoting prime numbers

Constraints
1 ≤ t<10
1 ≤ n ≤ 1000

SAMPLE INPUT
1
3
2 3 5

SAMPLE OUTPUT
4

Explanation

Xor of Subset of [2,3,5] are:
xor{0}=0,
xor{2}=2,
xor{3}=3,
xor{5}=5,
xor{2,3}=1,
xor{3,5}=6,
xor{2,5}=7,
xor{2,3,5}=4
Now,total no of distinct prime numbers are 4 i.e 2,3,5,7

见题面

见题面