题目描述

小明在数学书里找到了一组数据$a_1,a_2,...,a_n$ 这一组数据里的每个数字都有个特点——这里面的每个数的值只有可能是1、2和4。小明想让你帮他找到找到一个最小的正整数 $z$，使之满足：

1、$1≤z≤n-1$

2、$a_1·a_2·...·a_z=a_{z+1}·a_{z+2}·...·a_{n}$

输入格式

第一行输入一个 $t$，表示有 $t$ 组数据。( $1≤t≤10$ ). 每组数据的第一行输入一个 $n$ ( $2 \leq n \leq 100000$ ). 后面一行输入 $n$ 个整数$a_1, a_2, \ldots, a_n$ ($a_i = 1,2,4$).

输出格式

找不到 $z$ 输出 $-1$. 否则输出满足条件的 $z$ 的最小值。

样例 #1

样例输入 #1

2
7
2 4 1 2 1 2 2
3
1 4 1

样例输出 #1

2
-1

提示

就是找一个最小的整数 $z$,使满足 $z$ 及其前面的乘积和其之后的乘积相等。

样例1解释：

样例1共有2组数据，第一组数据有7个数据元素，由于$2 * 4==1 * 2 * 1 * 2 *2$，$4$的下标是$a[2]$,所以结果输出了2，第二组数据有3个数据元素，由于在哪个位置去算$z$前面的乘积和$z$后面的乘积都无法找到相等的情况，所以找不到$z$ 输出的$-1$ 。