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 (1 ≤ t ≤ 2500) - the number of test cases. Each of the next t lines contains one integer n (2 ≤ n ≤ 109).

Output

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