Combinatory logic is a symbolic system invented by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. This problem examines a combinatory system that differs slightly from real-world combinatory calculus.

A combinatory term is one of the following forms:

• $P$
• $(E_1\;E_2)$

where $P$ denotes a basic function, and $E_1$ and $E_2$ denote combinatory terms (which may be identical). Expressions that do not satisfy these forms are not combinatory terms.

We define the number of parameters $np(E)$ of a combinatory term $E$ as follows:

• $np(P)$ = the number of parameters of the basic function $P$;
• $np((E_1\;E_2)) = np(E_1) - 1$.

In this problem, we use a positive integer to represent both a basic function and the number of parameters of that basic function.

For a combinatory term $E$, if the number of parameters $np$ of $E$ and all combinatory terms contained within it are positive integers, we call $E$ a normal form.

We often use a simplified representation for combinatory terms: if a combinatory term $E$ contains a consecutive subsequence $(… ((E_1\;E_2)\;E_3) …E_n)$ (where $n \ge 3$), where $E_k$ denotes a combinatory term (which may be in simplified representation), then replacing this part with $(E_1\;E_2\;E_3 … E_n)$ while leaving other parts unchanged results in a simplified representation of the expression $E$. A combinatory term can be simplified multiple times.

Given a sequence of basic functions, determine the minimum number of pairs of parentheses that must be added to make the expression a simplified representation of a normal form (i.e., satisfying the properties of a normal form). If it is impossible to obtain a simplified representation of a normal form regardless of how parentheses are added, output $-1$.

Input

The first line contains a positive integer $T$, representing the number of queries.

The next $2T$ lines follow.

The $2k$-th line contains a positive integer $n_k$, representing the number of basic functions in the $k$-th query.

The $2k + 1$-th line contains $n_k$ positive integers, where the $i$-th integer represents the $i$-th basic function in the sequence.

Output

Output $T$ lines, each containing an integer representing the result for the corresponding query.

Examples

Input 1

2
5
3 2 1 3 2
5
1 1 1 1 1

Output 1

3
-1

Note 1

For the first query: An optimal solution is (3 (2 1) (3 2)). It can be proven that no solution exists with fewer pairs of parentheses.

For the second query: It is easy to prove that no valid solution exists.

Constraints

Let $TN$ be the sum of all $n_k$ in the input.