The night sky was clear, and the moon reflected beautifully off the quiet ocean. Nami and Samer Samora sat close together on the deck of the Sunny. Samer Samora looked into Nami's eyes, gently took her hand, and promised to share all his adventures, treasures, and even his debts with her.
They mapped out their future using a cyclic array $$$a_{1}, a_{2}, \dots, a_{n}$$$ that sums to 0. A rotation represents a possible starting point for their new life, reading all $$$n$$$ items in a circle.
Because Nami loves money and Samer Samora deeply loves Nami, he wants to ensure she never feels insecure. A rotation is considered "safe" if their shared wealth (the prefix sums) never drops below zero. Help Samer Samora count the number of safe starting points so he can give Nami the perfect, secure, happy ending they deserve.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \times 10^{5}$$$) — the number of balance changes.
The second line contains $$$n$$$ integers $$$a_{1}, a_{2}, \dots, a_{n}$$$ ($$$-10^{9} \le a_{i} \le 10^{9}$$$) — the balance changes around the table.
It is guaranteed that $$$\sum_{i=1}^{n}a_{i}=0$$$ for each test case, and the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^{5}$$$.
For each test case, output one integer — the number of safe rotations.
231 -1 03-1 1 0
21
In the first test case, the safe rotations are [1, -1, 0] and [0, 1, -1].
In the second test case, only the rotation [1, 0, -1] is safe.
