Sean is proud of his knowledge in mathematics and is always seen boasting about it everywhere. One day Sean's friend Mary gave him a challenge, and since Mary was a girl Sean had crush on, Sean accepted her challenge without querying further what was it about.

In the challenge, Mary gives Sean a set of integers, and asks the total number of subsets of that set containing positive number of elements, sum of all elements of which equals zero. Since the total number could be very large, Sean is a little bit of afraid of solving this task by himself and seeks your help.

Input:
The first line of input contains the number of test cases t, 2*t lines follow.

For each test case, the first line contains a positive number n, the number of elements in the set.
The second line consists of n integers separated by a single space. i'th integer is denoted by a[i].
Output:
For each test case, output the required answer on a separate line.
Constraints:

1 ≤ t ≤ 5
1 ≤ n ≤ 40
|a[i]| ≤ 1000000000

SAMPLE INPUT
1
4
2 3 -2 -1

SAMPLE OUTPUT
2

Explanation

In the given example, there are only 2 subsets that satisfy the given condition and they are, {2, -2} and {3, -2, -1}

见题面

见题面