Игра

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

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

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

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

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

Примеры