eolymp
bolt
Try our new interface for solving problems

Game

Time limit 1 second
Memory limit 128 MiB

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 (1t2500) - the number of test cases. Each of the next t lines contains one integer n (2n10^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
Source IZHO 2019 Selection Contest, Dec. 29 2018, Baku