There are $n$ players playing a game at a circular table. The $i$-th player has $a_i$ dishes to eat. They take turns eating the food, and any player can go first.

During their turn, if player $i$ has any dishes remaining, they must eat exactly one dish. Then, player $(i \bmod n) + 1$ starts their turn. This continues until all dishes are finished.

The player who eats the last dish is considered the winner. Determine the number of players that can possibly be winners.

Input

The first line contains an integer $t$ ($1 \leq t \leq 5000$), the number of test cases.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 10$).

The second line of each test case contains $n$ integers, the elements of $a$ ($1 \leq a_i \leq 10$).

Output

For each test case, output a line with the answer.

Note

In the first test case, player $1$ wins for every starting player.

In the second test case, player $2$ wins for every starting player.

In the third test case, players $2$ and $4$ can win.

Samples

3
1
10
2
6 7
4
1 4 3 4

1
1
2