17 months ago

Abhilash Kalyanakrishnan • 300

Billy has an array of size n of positive integers. He tries to modify the elements of the array in the following
manner:

In each step, he picks any two elements of the array, i, j (1 < i,j {n; i ≠ j), such that both a; and a; are positive:

1)If a_i > a_j : replace a; by a; + a; and replace a_j by 0.
2)If a_i < a_j : replace a; by 0 and replace a; by a_j + a_i.
3)If a_i = a_j : replace any one by a_i + a_j and the other with 0.

He performs the above step multiple times. Soon he realizes that, after a finite number of steps, always, all
the elements of the array except one will become 0 and the only non-zero element will actually contain the
sum of the elements of the array. Billy is really fascinated by this observation. He calls this position which
holds the non-zero sum of elements to be an eligible position. He now wonders how many positions in the
array are eligible. He finds it too hard to find it out himself, so he asks for your help.

Input Format

First line contains a single integer t -- the number of test cases. Each test case consists of two lines, the first
line contains n, the number of elements of the array. The seconds line of each test case consists of n space
separated positive integers a₁, a₂, a₃, ... a_n, the elements of the array.

Constraints

(1 < t < 10³)
(1 < n < 10⁵)
(1 ≤ a_i < 10⁹)

Output Format

For each test case, print in a new line, a single integer k - - the number of eligible positions of the array.

 

Sample Input 0


3
3
1 9 8
5
1 2 3 4 10000
4
2 2 2 2


Sample Output 0
2

1

4

Explanation 0

In the first test case, only az or a can hold 18 (1 + 8 + 9) after certain number of steps. a can not hold 18.
In the second test case, only as can hold the sum of elements.
In the third test case, every index can hold the sum.