Game#8674
Murad and Ibrahim are playing a game. Initially, the number is given. On each turn, a player must multiply the current number by one of the integers from to (inclusive). The goal is to obtain a number not less than the given integer . The first player to obtain such a number is declared the winner. Murad always starts first. Determine who will win if both Murad and Ibrahim play optimally.
The first line contains one integer (1 \leq t \leq 2500) — the number of test cases. Each of the next lines contains one integer (2 \leq n \leq 10^9).
For each test case, print in a separate line 1 if Murad will win the game, or 2 otherwise.
Example 1