Suffix Cutting

Limits 1s, 512 MB

You are given an array aa consisting of nn integers a1,a2,....,ana_1, a_2,...., a_n.

The array is called beautiful if all prefix sums of the array are non-negative. Formally, the array is beautiful if:

An index i(1in)i(1 \le i \le n) of the array is good, if we cut the suffix starting at index ii from the array and append the suffix at the beginning of the array, the array becomes beautiful. Formally, an index ii is good if:

Find the number of good indices of array aa.

Input

Each input consists of multiple test cases. The first line contains a single integer t(1t2×105)t(1 \le t \le 2\times 10^5) the number of sets of input data. This is followed by their description.

The first line of each test case contains a single integer n (1n2×105)n\space(1 \le n \le 2\times 10^5) the size of the array aa.

The second line of each test case contains nn space seperated integers a1,a2,,ana_1,a_2,…,a_n denoting the array aa(104ai104)(-10^4 \le a_i \le 10^4).

It is guranteed that sum of nn of all test cases does not exceed 2×1052 \times 10^{5}.

Output

For each test case, output the number of good indices of the array in seperated lines.

Sample

InputOutput
2
5
5 4 -1 -2 3
3
-1 -2 -3
3
0

In the first test case there are 3 good indices {1, 2, 5}.

Index 1 is good. If we select index 1, the array becomes {5, 4, -1, -2, 3}. The prefix sums of the array are {5, 9, 8, 6, 9}. All the elements of prefix sums are non-negative.

Index 2 is good. If we select index 2, the array becomes {4, -1, -2, 3, 5}. The prefix sums of the array are {4, 3, 1, 4, 9}. All the elements of prefix sums are non-negative.

Index 3 is not good. If we select index 3, the array becomes {-1, -2, 3, 5, 4}. The prefix sums of the array are {-1, -3, 0, 5, 9}. There are two negative prefix sums.