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 of the input 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.