Time Limit: 1000 MS    Memory Limit: 65536 K 


Description

Fisherman Zerg has caught N fish and brought them to the fish market. The people from fish market pack the fish in packages with different weights. Each package can have one or more fish. Suppose you are the first customer and you can choose the weight of your package. How many possible different weights of packages exist with these N fish?

Input

The first line of the input will be a integer to represent the number of test cases. For each test case there is two lines. The first line contains only one integer N. The second line contains N integers representing the weight of each fish. ( 1 <= N <= 30 , 1 <= weight <= 1000 ) There is a blank line before each test case.

Output

For each test case output the answer on a single line.

Sample Input

2 1 50 5 800 200 354 18 182

Sample Output

1 27

Source

zerg