A. Разноцветные шары: перезагрузка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Название — это отсылка на самый первый Educational Round нашего авторского коллектива, Educational Round 18.

Есть мешок, в котором лежат разноцветные шары. Всего есть $$$n$$$ различных цветов шаров, пронумерованные от $$$1$$$ до $$$n$$$. В мешке лежат $$$\mathit{cnt}_i$$$ шаров цвета $$$i$$$. Суммарное количество шаров в мешке нечетное (т. е. $$$\mathit{cnt}_1 + \mathit{cnt}_2 + \dots + \mathit{cnt}_n$$$ нечетное).

За один ход можно выбрать два шара разных цветов и вынуть их из мешка.

В какой-то момент все оставшиеся в мешке шары станут одного цвета. Тогда вы больше не можете делать ходы.

Найдите любой возможный цвет оставшихся шаров.

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

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

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 20$$$) — количество цветов.

Во второй строке записаны $$$n$$$ целых чисел $$$\mathit{cnt}_1, \mathit{cnt}_2, \dots, \mathit{cnt}_n$$$ ($$$1 \le \mathit{cnt}_i \le 100$$$) — количество шаров каждого цвета в мешке.

Суммарное количество шаров в мешке нечетное (т. е. $$$\mathit{cnt}_1 + \mathit{cnt}_2 + \dots + \mathit{cnt}_n$$$ нечетное).

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

На каждый набор входных данных выведите одно целое число — любой возможный цвет оставшихся шаров после того как вы сделали какие-либо ходы и больше не можете делать ходы.

Пример
Входные данные
3
3
1 1 1
1
9
2
4 7
Выходные данные
3
1
2
Примечание

В первом наборе входных данных ваш первый и единственный ход может быть одним из следующих:

  • возьмем шары с цветами $$$1$$$ и $$$2$$$;
  • возьмем шары с цветами $$$1$$$ и $$$3$$$;
  • возьмем шары с цветами $$$2$$$ и $$$3$$$.

После хода останется ровно один шар. Его цвет может быть $$$3, 2$$$ или $$$1$$$ в зависимости от хода.

Во втором наборе не получится сделать ход вообще — есть всего один цвет шаров. Этот цвет $$$1$$$.

В третьем примере можно удалять один шар цвета $$$1$$$ и один шар цвета $$$2$$$, пока не закончатся шары цвета $$$1$$$. В конце останутся три шара цвета $$$2$$$.