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