#1549 Symmetric Pie

41  10 s   128 MB  

Description

You've collected data in a int[] dogs which describes how many dogs are present in each neighborhood of your city, and you wish to represent this data in a pie chart. The total number of dogs in your city is exactly 100, so if a neighborhood has 15 dogs, it will form a solid region in the chart with an area equal to 15% of the whole pie chart.

Given a pie chart, a dividing line is a line that passes through the center of the chart and doesn't pass through the interior of any solid region of the chart. For example, the chart on the left has two dividing lines, while the chart on the right has only one dividing line.

Note that there may be several ways to create a pie chart from the same data. Print the maximum number of dividing lines in a pie chart that can be made from the data.

Input

The first line of the input gives a number of test cases, T (1 <= T <= 200).
The first line of each case gives a number of neighborhoods, N (1 <= N <= 8).
Next lines gives N integers which represents the number of dogs in each neighborhood.

Output

For each test case, output the maximum number of dividing lines.

Sample Input

Sample Output

2
4
10 40 10 40
3
10 50 40
2
1