eolymp

Гра

Мурад і Ібрагім грають у наступну гру. Спочатку є число 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