Por Costel the Pig has received a royal invitation to the palace of the Egg-Emperor of Programming, Azerah. Azerah had heard of the renowned pig and wanted to see him with his own eyes. Por Costel, having arrived at the palace, tells the Egg-Emperor that he looks "tasty". Azerah feels insulted (even though Por Costel meant it as a compliment) and, infuratied all the way to his yolk, threatens to kill our round friend if he doesn't get the answer to a counting problem that he's been struggling with for a while
Given an array of numbers, how many non-empty subsequences of this array have the sum of their numbers even ? Calculate this value mod 
(Azerah won't tell the difference anyway)
Help Por Costel get out of this mischief!
The file azerah.in will contain on its first line an integer 
, the number of test cases. Each test has the following format: the first line contains an integer 
(the size of the array) and the second line will contain 
integers 
(
), separated by single spaces.
It is guaranteed that the sum of over all test cases is at most 
The file azerah.out should contain lines. The 
-th line should contain a single integer, the answer to the -th test case.
2
3
3 10 1
2
4 2
3
3
