MG loves set

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

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”.

Sample Input

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

Sample Output

15 12 25

Hint

wange2014

Source

BestCoder Round #93

提交代码