Mike has a huge guitar collection which the whole band is jealous of. Brad, the lead guitarist of the band, gave Mike a challenge so that he can't use all his guitars. The band is on a world tour and Brad told Mike to assign numbers to all his guitars. After that, he told Mike that he can use the guitars in such a manner that no two concerts have the same sum when the numbers on the guitars used in that concert are added.
Now, Mike has other important things to do, like performing sound checks and last minute rehersals, and so he asks for your help. Help him find how many concerts will he be able to perform in this World Tour with the restrictions imposed on him by Brad .
Input: First line contains t, the number of test cases. Now, each test case consists of 2 lines, the first one contains N,the number of guitars that Mike has and the second line contains N space separated numbers assigned by Mike to his guitars denoted by a[i].
Output: For each test case you need to print a single integer denoting the number of concerts that Mike would be able to perform in this world tour.
Constraints:
1<=t<=20
1<=N<=20
1<=a[i]<=100
Problem Setter: Rohit Mishra
Consider the 3rd test case We have guitars numbered 1,2 and 3 So all the different possibilities are: {} - Sum=0 {1} - Sum=1 {2} - Sum=2 {3} - Sum=3 {1,2} - Sum=3 {1,3} - Sum=4 {2,3} - Sum=5 {1,2,3} - Sum=6
So, we see that 7 different sums are possible (3 is counted only once) and so output is 7.
