Задачи
Игра
Игра
Мурад и Ибрагим играют в следующую игру. Изначально дается число 1. На своем ходу каждый игрок должен умножить текущее число на одно из целых чисел от 2 до 9 включительно. Цель состоит в том, чтобы получить число не меньше заданного целого числа n. Игрок, получивший такой номер первым, объявляется победителем. Мурад всегда начинается первым. Выясните, кто победит, если Мурад и Ибрагим будут играть оптимально.
Входные данные
Первая строка содержит одно число t (1 ≤ t ≤ 2500) - количество тестов. Каждая из следующих t строк содержит одно целое число n (2 ≤ n ≤ 10^9
).
Выходные данные
Для каждого теста выведите в отдельной строке 1, если Мурад выиграет игру, и 2 иначе.
Пример
Входные данные #1
4 9 10 1149729 999999999
Выходные данные #1
1 2 2 1