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

Ни для кого не секрет, что в Валоранте агенты разыгрывают стороны до начала матча, и делают это именно Рейз и Брич, которые решили, что для этого надо сыграть $$$t$$$ партий следующей игры...

В каждой из $$$t$$$ партий игры сначала генерируется какое-то положительное целое число, состоящее из $$$n$$$ цифр. Цифры этого числа пронумерованы целыми числами от $$$1$$$ до $$$n$$$ от старшего разряда к младшему. После того, как число становится известно, начинается партия.

Агенты ходят по очереди, Рейз начинает первой. За один ход агент выбирает любую незакрашенную цифру и закрашивает её. Рейз может выбирать цифры на нечётных позициях, но не может на чётных, а Брич может выбирать цифры на чётных позициях, но не может на нечётных. Партия заканчивается тогда, когда остаётся одна незакрашенная цифра. Если единственная оставшаяся цифра нечётная, то выигрывает Рейз, иначе выигрывает Брич.

Можно доказать, что до того как партия закончится (при любом изначальном целом, состоящем из $$$n$$$ цифр), каждый агент будет иметь возможность сделать ход, то есть будет хотя бы одна незакрашенная цифра, стоящая на позиции нужной чётности.

Для каждой из $$$t$$$ партий определите, кто из агентов выиграет, если оба игрока хотят победить и действуют оптимально.

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

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

В первой строке описания каждой партии находится единственное целое число $$$n$$$ $$$(1 \le n \le 10^3)$$$  — количество цифр в числе, с которым будет проведена партия.

Во второй строке описания каждой партии находится целое положительное число, состоящее из $$$n$$$ цифр  — число, с которым будет проведена партия. Гарантируется, что это число без лидирующих нулей.

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

Для каждой партии выведите $$$1$$$, если выиграет Рейз, и $$$2$$$, если выиграет Брич.

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

В первой партии никто не может сделать ход, единственная оставшаяся цифра  — это $$$2$$$, она четная, поэтому выигрывает Брич.

Во второй партии единственная оставшаяся цифра  — это $$$3$$$, она нечётная, поэтому выигрывает Рейз.

В третьей партии Рейз может закрасить последнюю цифру, после чего Брич может закрасить только $$$0$$$. Останется только цифра $$$1$$$, и она нечётная, поэтому выигрывает Рейз.

В четвертой партии вне зависимости от игры Рейз, Брич может закрасить $$$9$$$, и в конце игры останется $$$0$$$  — чётная цифра, поэтому выигрывает Брич.