A. Единицы и двойки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность $$$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$$$.

Пример
Входные данные
3
6
2 2 1 2 1 2
3
1 2 1
4
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$$$.