组合子逻辑是 Moses Schönfinkel 和 Haskell Curry 发明的一种符号系统，用于消除数理逻辑中对于变量的需要。本题考察一种与真实世界的组合子演算略有差别的组合子系统。
一个组合子项是下列形式之一：
- $P$
- $(E_1\;E_2)$
其中 $P$ 表示一个基本函数，$E_1$ 以及 $E_2$ 表示一个组合子项（可以相同）。不满足以上形式表达式均非组合子项。
我们将一个组合子项 $E$ 的参数个数 $np(E)$如下：
- $np(P)$ = 基本函数 $P$ 的参数个数；
- $np((E_1\;E_2)) = np(E_1) - 1$。
本题中，我们用一个正整数同时表示一个基本函数，以及该基本函数的参数个数。
对于一个组合子项 $E$，如果它和它包含的所有组合子项的参数个数 $np$ 均为正整数，那么我们称这个 $E$ 为范式。
我们经常组合子项简化表示：如果一个组合子项$E$含有连续子序列$(… ((E_1\;E_2)\;E_3) …E_n)$ (其中 $n ≥ 3$)，其中$E_k$表示组合子项(可以是简化表示的)，那么将该部分替换为$(E_1\;E_2\;E_3 … E_n)$，其他部分不变，得到表达式 $E$ 的一个简化表示。一个组合子项可以被简化表示多次。
给定一个基本函数序列，问至少需要添加多少对括号，才能使得该表达式成为一个范式的简化表示（即满足范式的性质）；如果无论如何怎样添加括号，均不能得到范式的简化表示，输出$-1$。
输入格式
第一行包含一个正整数 $T$，表示有 $T$ 次询问。
接下来 $2T$ 行。
第 $2k$ 行有一个正整数$n_k$，表示第 $k$ 次询问的序列中基本函数的个数。
第 $2k + 1$ 行有$n_k$个正整数，其中第 $i$ 个整数表示序列中第 $i$ 个基本函数。
输出格式
输出 $T$ 行，每行一个整数，表示对应询问的输出结果。
样例数据
样例输入
2 5 3 2 1 3 2 5 1 1 1 1 1
样例输出
3 -1
样例解释
第一次询问：一个最优方案是(3 (2 1) (3 2))。可以证明不存在添加括号对数更少的方案。
第二次询问：容易证明不存在合法方案。
数据规模和约定
令 $TN$ 表示输入中所有$n_k$的和。
| 测试点编号 | 规模 |
|---|---|
| 1 | $T ≤ 30,n_k ≤ 3$ |
| 2 | $T ≤ 30,n_k ≤ 15$ |
| 3 | $TN ≤ 100$ |
| 4 | $TN ≤ 500$ |
| 5 | $TN ≤ 2000$ |
| 6 | $TN ≤ 5000$ |
| 7 | $TN ≤ 5000$ |
| 8 | $TN ≤ 1000000$ |
| 9 | $TN ≤ 2000000$ |
| 10 | $TN ≤ 2000000$ |