Один математик решил проверить, какое число счастливее – 7 или 13. Для этого он берет случайную последовательность N целых чисел и последовательно преобразовывает ее в единственное число за N-1 шаг.

На K-ом шаге математик удаляет из последовательности два числа A и B и добавляет к последовательности число следующим образом:

1. Сперва математик выбирает из последовательности число с порядковым номером (это A) и удаляет его из последовательности.

2. Затем он выбирает число с порядковым номером (это B) и удаляет его из последовательности.

3. После этого математик дописывает число в начало последовательности.

После N-1 шага в последовательности останется одно число. Если это число четное, то число 7 более счастливое. Если это число нечетное, то число 13 более счастливое.

Формат ввода/вывода:

Напишите программу FORTUNE, которая читает с клавиатуры последовательность тестов и для каждого теста выводит на экран более счастливое число.

В первой строке ввода находится число T – количество тестов. В последующих 2T строках находятся данные тестов. j-ый тест состоит из двух строк, в первой строке находится число – количество элементов последовательности, во второй строке находится чисел – элементы последовательности .

Для каждого теста на экран должно быть выведено более счастливое число – 7 или 13 – определенное по соответствующей последовательности чисел.

Ограничения: ,,

Пример:

Ввод:

2
7
1 2 3 4 5 6 7
13
13 12 11 10 9 8 7 6 5 4 3 2 1

Вывод:

7
13