A. Контест Монокарпа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп составляет командный контест по программированию. В контесте есть $$$n$$$ задач, каждая из которых является либо простой, либо сложной. Задачи пронумерованы от $$$1$$$ до $$$n$$$.

Монокарп хочет, чтобы первая и последняя задачи контеста были простыми. За одну операцию он может выбрать любые две задачи и поменять их местами.

Определите минимальное количество операций, необходимое для того, чтобы первая и последняя задачи стали простыми, либо сообщите, что это невозможно.

Входные данные

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк

  • первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 50$$$) — количество задач в контесте;
  • вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$). Если $$$a_i=0$$$, то задача с номером $$$i$$$ простая; если $$$a_i=1$$$, то она сложная.
Выходные данные

Для каждого набора входных данных выведите минимальное количество операций, необходимое для того, чтобы первая и последняя задачи стали простыми. Если выполнить требование невозможно, выведите $$$-1$$$.

Пример
Входные данные
4
2
0 0
2
0 1
6
1 0 0 1 0 0
5
1 0 0 1 1
Выходные данные
0
-1
1
2
Примечание

В первом наборе входных данных первая и последняя задачи уже простые, поэтому операций не требуется.

Во втором наборе входных данных простая задача только одна, поэтому сделать простыми обе крайние задачи невозможно.

В третьем наборе входных данных можно поменять местами первую и вторую задачи.

В четвёртом наборе входных данных можно сначала поменять местами первую и вторую задачи, а затем — третью и пятую.