В вузе ИТ-града существует такая легенда. Студенту, не ответившему ни на один вопрос на экзамене по теории игр, преподаватель даёт последний шанс. Студенту нужно сыграть с преподавателем в игру.
Игра происходит на квадратном клетчатом поле n × n. Изначально все клетки поля пусты. На каждом ходу игрок выбирает пустую клетку, не имеющую общих сторон с закрашенными клетками, и закрашивает её. Касание закрашенных клеток углами допускается. На следующем ходу то же самое делает второй игрок, после него первый и так далее. Тот, кому некуда сделать ход, проигрывает.
Преподаватель уже выбрал размер поля n и предоставил студенту выбор ходить первым или вторым. Что должен выбрать студент, чтобы выиграть в игре? Будем считать, что оба игрока играют оптимально.
Выходные данные
Выведите число 1, если при оптимальной игре обоих игроков выиграет игрок, делающий первый ход, иначе число 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
|
|
2
|
2
|
2
|