Problems
Game
Game
Murad and Ibrahim are playing in the next game. Initially, number 1 is given. On his turn, each player must multiply the current number by one of integers between 2 and 9, inclusively. The goal is to obtain a number not less than the given integer n. Player, who obtained such a number first, is declared as the winner. Murad always starts first. Find out, who will win if Murad and Ibrahim will play optimally.
Input data
The first line contains one integer t (1 ≤ t ≤ 2500) - the number of test cases. Each of the next t lines contains one integer n (2 ≤ n ≤ 10^9
).
Output data
For each test case print in a separate line 1, if Murad will win the game, and 2 otherwise.
Examples
Input example #1
4 9 10 1149729 999999999
Output example #1
1 2 2 1