Two players are playing the following game with a positive integer N. On his turn a player has to write down on paper some integer between 1 and N. But it's forbidden to write an integer which is a divisor of some number already written on paper. For example N = 8 and numbers already written are: 6, 4, 7. In this case the new integer can be only 5 or 8.

If a player can not write a new number on his turn then he loses. Given the integer N can you figure out who will win the game if we assume that both players play optimally?

Input

The first line contains T - the number of test cases. The following T lines contain one integer N each for the following test case.

Output

For each test case output 1 or 2 on a separate line depending on the answer for this test case.

Constraints

• 1 <= T, N <= 30

Subtasks

• 1 <= T <= 5, 1 <= N <= 10 in 40% of test data.