e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

Игра

Игра

Мурад и Ибрагим играют в следующую игру. Изначально дается число 1. На своем ходу каждый игрок должен умножить текущее число на одно из целых чисел от 2 до 9 включительно. Цель состоит в том, чтобы получить число не меньше заданного целого числа n. Игрок, получивший такой номер первым, объявляется победителем. Мурад всегда начинается первым. Выясните, кто победит, если Мурад и Ибрагим будут играть оптимально.

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

Первая строка содержит одно число t (1t2500) - количество тестов. Каждая из следующих t строк содержит одно целое число n (2n109).

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

Для каждого теста выведите в отдельной строке 1, если Мурад выиграет игру, и 2 иначе.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4
9
10
1149729
999999999
Выходные данные #1
1
2
2
1
Источник IZHO 2019 Selection Contest, Dec. 29 2018, Baku