Problems

# Game

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

).^{9}

#### Output

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

Input example #1

4 9 10 1149729 999999999

Output example #1

1 2 2 1