Ни для кого не секрет, что в Валоранте агенты разыгрывают стороны до начала матча, и делают это именно Рейз и Брич, которые решили, что для этого надо сыграть \(t\) партий следующей игры...
В каждой из \(t\) партий игры сначала генерируется какое-то положительное целое число, состоящее из \(n\) цифр. Цифры этого числа пронумерованы целыми числами от \(1\) до \(n\) от старшего разряда к младшему. После того, как число становится известно, начинается партия.
Агенты ходят по очереди, Рейз начинает первой. За один ход агент выбирает любую незакрашенную цифру и закрашивает её. Рейз может выбирать цифры на нечётных позициях, но не может на чётных, а Брич может выбирать цифры на чётных позициях, но не может на нечётных. Партия заканчивается тогда, когда остаётся одна незакрашенная цифра. Если единственная оставшаяся цифра нечётная, то выигрывает Рейз, иначе выигрывает Брич.
Можно доказать, что до того как партия закончится (при любом изначальном целом, состоящем из \(n\) цифр), каждый агент будет иметь возможность сделать ход, то есть будет хотя бы одна незакрашенная цифра, стоящая на позиции нужной чётности.
Для каждой из \(t\) партий определите, кто из агентов выиграет, если оба игрока хотят победить и действуют оптимально.
Выходные данные
Для каждой партии выведите \(1\), если выиграет Рейз, и \(2\), если выиграет Брич.
Примечание
В первой партии никто не может сделать ход, единственная оставшаяся цифра — это \(2\), она четная, поэтому выигрывает Брич.
Во второй партии единственная оставшаяся цифра — это \(3\), она нечётная, поэтому выигрывает Рейз.
В третьей партии Рейз может закрасить последнюю цифру, после чего Брич может закрасить только \(0\). Останется только цифра \(1\), и она нечётная, поэтому выигрывает Рейз.
В четвертой партии вне зависимости от игры Рейз, Брич может закрасить \(9\), и в конце игры останется \(0\) — чётная цифра, поэтому выигрывает Брич.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
2
1
3
3
102
4
2069
|
2
1
1
2
|