eolymp

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

The first line contains one integer t (1t2500) - the number of test cases. Each of the next t lines contains one integer n (2n109).

Output

For each test case print in a separate line 1, if Murad will win the game, and 2 otherwise.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4
9
10
1149729
999999999
Output example #1
1
2
2
1
Source IZHO 2019 Selection Contest, Dec. 29 2018, Baku