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ˇ±.
