Problem Description

MG is an intelligent boy. One day he was challenged by the famous master called Douer:
if the sum of the square of every element in a set is less than or equal to the square of the sum of all the elements, then we regard this set as ”A Harmony Set”.

Now we give a set with $n$ different elements, ask you how many nonempty subset is “A Harmony Set”.

MG thought it very easy and he had himself disdained to take the job. As a bystander, could you please help settle the problem and calculate the answer?

Input

The first line is an integer $T$ which indicates the case number.($1<=T<=10$)

And as for each case, there are $1$ integer $n$ in the first line which indicate the size of the set($n<=30$).

Then there are $n$ integers $V$ in the next line, the x-th integer means the x-th element of the set($0<=|V|<=100000000$).

Output

As for each case, you need to output a single line.

There should be one integer in the line which represents the number of “Harmony Set”.

3
4
1 2 3 4
5
1 -1 2 3 -3
6
0 2 4 -4 -5 8

15
12
25