Problem Statement

A sequence that can be obtained as $A$ by performing the following operations is called a special sequence:

• Prepare an undirected graph consisting of $N$ vertices and $0$ edges, and a sequence $A$ of length $0$.
• Prepare queries for integers $i,j$ satisfying $1 \leq i < j \leq N$ and $q \in \{1,2\}$:
• There are $N(N-1)$ possible queries; rearrange them in any order and process them in that order.

You are given a sequence $B$ of length $\frac{N(N-1)}{2}$ consisting of $0$ and $1$. You can perform the following operation on $B$ any number of times:

• Choose an integer $i$ satisfying $1 \leq i \leq \frac{N(N-1)}{2}-1$, and swap $B_i$ and $B_{i+1}$.

Determine whether it is possible to make $B$ a special sequence, and if possible, find the minimum number of operations required.

Solve $T$ test cases per input.

Constraints

• $1 \leq T$
• $2 \leq N \leq 500$
• $|B| =\frac{N(N-1)}{2}$
• $0 \leq B_i \leq 1$
• The sum of $|B|$ over all test cases is at most $3 \times 10^5$.
• The sum of $N^3$ over all test cases is at most $500^3$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is given in the following format:

N
B_1 B_2 \ldots B_{\frac{N(N-1)}{2}}

Output

Output $T$ lines in total. The $t$-th line should contain the minimum number of operations required to make $B$ a special sequence for the $t$-th test case if it is possible to do so, and -1 otherwise.