eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Игра

Игра

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

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

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

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

Пример

Входные данные #1
4
9
10
1149729
999999999
Выходные данные #1
1
2
2
1
Источник IZHO 2019 Selection Contest, Dec. 29 2018, Baku