← Home
write a go solution for Description:
Alex thinks some array is good if there exists some element that can be represented as the sum of all other elements (the sum of all other elements is 0 if there are no other elements). For example, the array [1,6,3,2] is good since 1+3+2=6. Furthermore, the array [0] is also good. However, the arrays [1,2,3,4] and [1] are not good.

Alex has an array a_1,a_2,ldots,a_n. Help him count the number of good non-empty prefixes of the array a. In other words, count the number of integers i (1<=i<=n) such that the length i prefix (i.e. a_1,a_2,ldots,a_i) is good.

Input Format:
The first line of the input contains a single integer t (1<=t<=10^4) — the number of test cases.

The first line of each test case contains a single integer n (1<=n<=2*10^5) — the number of elements in the array.

The second line of each test case contains n integers a_1,a_2,ldots,a_n (0<=a_i<=10^9) — the elements of the array.

It is guaranteed that the sum of n over all test cases does not exceed 2*10^5.

Output Format:
For each test case, output a single integer — the number of good non-empty prefixes of the array a.

Note:
In the fourth test case, the array has five prefixes:

- prefix [0] is a good array, as mentioned in the statement;
- prefix [0,1] is not a good array, since 0ne1;
- prefix [0,1,2] is not a good array, since 0ne1+2, 1ne0+2 and 2ne0+1;
- prefix [0,1,2,1] is a good array, since 2=0+1+1;
- prefix [0,1,2,1,4] is a good array, since 4=0+1+2+1.

As you can see, three of them are good, so the answer is 3.. Output only the code with no comments, explanation, or additional text.