给定一个序列 $$$a_1, a_2, \ldots, a_n$$$。 $$$a$$$ 的每个元素都是 $$$1$$$ 或 $$$2$$$。
找出整数 $$$k$$$ 是否存在且满足以下条件。
- $$$1 \leq k \leq n-1$$$,并且
- $$$a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n$$$。
如果存在多个满足给定条件的$$$k$$$,则打印最小的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 1000$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2$$$)。
输出
对于每个测试用例,如果没有这样的$$$k$$$,则打印$$$-1$$$。
否则,打印尽可能小的$$$k$$$。
示例
输入 #1
3 6 2 2 1 2 1 2 3 1 2 1 4 1 1 1 1
输出 #1
2 -1 1
注意
对于第一个测试用例,$$$k=2$$$ 满足条件,因为 $$$a_1 \cdot a_2 = a_3 \cdot a_4 \cdot a_5 \cdot a_6 = 4$$$。 $$$k=3$$$ 也满足给定条件,但应该打印最小的。
对于第二个测试用例,没有 $$$k$$$ 满足 $$$a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n$$$
对于第三个测试用例,$$$k=1$$$、$$$2$$$ 和 $$$3$$$ 满足给定条件,因此答案为 $$$1$$$。