Мурад і Ібрагім грають у наступну гру. Спочатку є число 1. Потім по черзі, кожен гравець повинен помножити поточне число на одне з цілих чисел від 2 до 9 включно. Завданя полягає в тому, щоб отримати число не менше заданого цілого числа n. Гравець, який першим отримав таке число, стає переможцем. Мурад завжди починає першим.

Дізнайтеся, хто виграє, якщо Мурад і Ібрагім будуть грати оптимально.

Вхідні дані

Перший рядок містить одне ціле число t (1 ≤ t ≤ 2500) - кількість тестів. Кожен з наступних t рядків містить одне ціле число n (2 ≤ n ≤ 109).

Вихідні дані

Для кожного тесту виведіть в окремому рядку 1, якщо Мурад виграє гру, і 2 в іншому випадку.