Suffix Cutting

You are given an array $a$ consisting of $n$ integers $a_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:

• $\sum\limits_{i=1}^{k}a_i\ge 0$ for $1 \le k \le n$.

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

• The array $\{a_i,a_{i+1},….,a_n,a_1,a_2,….,a_{i-1}\}$ is beautiful.

Find the number of good indices of array $a$.

Input

Each input consists of multiple test cases. The first line contains a single integer $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\space(1 \le n \le 2\times 10^5)$ the size of the array $a$.

The second line of each test case contains $n$ space seperated integers $a_1,a_2,…,a_n$ denoting the array $a$$(-10^4 \le a_i \le 10^4)$.

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

Output

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

Sample

Input	Output
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.