M. Siteswap
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Siteswap (https://en.wikipedia.org/wiki/Siteswap) is a juggling notation that allows to represent juggling patterns.

In siteswap, it is assumed that throws happen by two alternating hands on beats that are equally spaced in time. A siteswap pattern is a sequence of numbers in which throws are represented by non-negative integers that specify the number of beats in the future after which the object is caught and thrown again.

In other words, a siteswap pattern is a sequence $$$a_1, a_2, \dots, a_n$$$, in which $$$a_k$$$ describes the throw made on the $$$k$$$-th beat and means that the object is caught and thrown again after $$$a_k$$$ seconds, that is, on the $$$(k+a_k)$$$-th second.

For example, the number $$$1$$$ means that the object is passed to the other hand to be thrown immediately on the next turn, and the number $$$2$$$ means that the next throw with the same hand happens with the same object. The special number $$$0$$$ in the pattern is used to denote that the hand is empty on the corresponding beat. See notes for more examples.

A siteswap pattern is valid if it can be repeated indefinitely in such way that each beat the current hand catches and then immediately throws at most one object.

For each valid pattern, it is possible to uniquely identify the number of objects needed to perform it. We may further classify these objects into those that eventually change the hand they're thrown with and those that do not. Given a valid siteswap pattern, find the number of objects that do not change the hand for each hand, and the number of objects that do change hand.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the siteswap pattern.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — a valid siteswap pattern.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output three numbers.

  1. The number of objects that are only thrown by the first hand (i. e. only on odd beats).
  2. The number of objects that are only thrown by the second hand (i. e. only on even beats).
  3. The number of objects that are thrown by both hands.
.
Example
Input
3
3
1 5 0
6
4 6 4 0 4 0
2
6 4
Output
0 0 2
2 1 0
3 2 0
Note

The pattern $$$1~5~0$$$ requires $$$2$$$ objects, each alternating hands:

Note that a throw is skipped once in a while because of the $$$0$$$ in the pattern. On the juggling animation you may detect it from the fact that the same hand is used twice in a row, and on the diagram it's depicted by the grey sections.

The pattern $$$4~6~4~0~4~0$$$ requires $$$3$$$ objects, $$$2$$$ in one hand and $$$1$$$ in the other:

Illustrations are by Siteswap Explorer: https://siteswapexplorer.com/.

For contestants using printed or PDF statements: these illustrations are animated. Please refer to the statements in the contest system to look at the animations.