给定一个序列 $a_1,a_2,\dots,a_n$，其中每个元素都等于 $1$ 或 $2$。

判断是否存在一个整数 $k$ 使得同时满足：

• $1 \le k \le n-1$；
• $a_1\cdot a_2\cdots a_k = a_{k+1}\cdot a_{k+2}\cdots a_n$。

如果存在多个满足条件的 $k$，输出其中最小的 $k$；若不存在，输出 $-1$。

输入格式

输入包含多组测试用例。

• 第一行一个整数 $t$（$1 \le t \le 100$），表示测试用例数量。

• 每个测试用例：

  • 第一行一个整数 $n$（$2 \le n \le 1000$）；
  • 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 2$），每个元素为 $1$ 或 $2$。

输出格式

对每个测试用例：

• 若不存在这样的 $k$，输出 -1；
• 否则输出满足条件的最小 $k$。

样例

输入

3
6
2 2 1 2 1 2
3
1 2 1
4
1 1 1 1

输出

2
-1
1