A. Bluff
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alex prepared a report with the help of the generative artificial intelligence CloseLoseShallow (CLS). His report contains $$$n$$$ statements $$$a_1, a_2, \dots, a_n$$$, and he is getting ready to present them to the audience.

Berta believes that most of these statements are false, but she only has evidence for some of them. For each statement, she knows for sure whether it is false or if she does not have enough information to refute it.

Every time Alex reads a statement, Berta will declare it false. If Berta can provide the proof, she will earn a point; if not, Alex will earn a point. If the fact that it is proven false does not prevent Alex from continuing to win, then Alex will not ask for any proof and will simply accept that it is false, giving a point to Berta; otherwise, he will ask for proof and earn a point.

Formally, if Berta has $$$b$$$ points and Alex has $$$a$$$ points, as long as $$$a \gt b + 1$$$, Berta will declare a statement false and her point total will be $$$b + 1$$$ (since Alex will not ask for a reference and both will accept that the statement is false).

Berta wants to ensure that, after her talk with Alex, she has more points than he does to demonstrate that generating reports with generative artificial intelligence is not a good idea. To achieve this, she can choose where to start reading the report and when to stop reading.

Formally, from the $$$n$$$ statements of Alex, Berta can choose a segment defined by the indices $$$l$$$ and $$$r$$$ ($$$l \leq r$$$) and calculate who earns more points in that interval with the statements $$$a_l, a_{l+1}, \dots, a_r$$$.

Berta wants to know how many intervals $$$[l, r]$$$ exist in which she earns more points than Alex. Can you help her calculate it?

Input

The first line of the input contains the number of cases $$$T$$$.

Each case begins with a line containing a single integer, $$$n$$$.

The next line of each case contains $$$n$$$ integers; if Berta has a refutation for the $$$i$$$-th statement, this value will be 1; otherwise, it will be 0.

Output

For each case, print a single line with an integer, the number of intervals in which Berta will earn more points than Alex.

Scoring
  1. (13 points) The sum of $$$n$$$ over all cases will be less than 100.
  2. (9 points) The sum of $$$n$$$ over all cases will be less than 2000.
  3. (18 points) The statements for which Berta has a refutation and those for which she does not alternate. (There is an example of this subtask explained in the notes of the example cases).
  4. (26 points) The sum of the number of statements for which Berta has a refutation across all cases is less than or equal to 300.
  5. (34 points) No additional restrictions.
Example
Input
3
2
1 1
5
0 1 0 1 0
6
1 0 0 1 0 1
Output
3
3
4
Note

$$$1 \le T \le 10^4$$$.

$$$1 \le n \le 10^6$$$.

The sum of $$$n$$$ for all cases is at most $$$10^6$$$.