J. Game with stones
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

There are $$$N$$$ stones in a pile. Two players take turns. On each turn, a player can take from $$$1$$$ to $$$K$$$ stones, but cannot take the same amount as their opponent took on the previous turn. The player who cannot make a move loses. Determine who will win if both players play optimally.

Input

The first line of input contains an integer $$$T$$$ — the number of game rounds ($$$1 \le T \le 10$$$). The next $$$T$$$ lines contain two integers $$$N_i$$$ and $$$K_i$$$ each ($$$2 \le N_i \le 5000$$$, $$$2 \le K_i \le N_i$$$).

Output

For each round, output 1 on a separate line if the first player wins, and 2 if the second player wins.

Example
Input
2
4 2
4 3
Output
1
2
Note

In the example, for $$$N=4$$$, $$$K=2$$$, the first player wins. He will take one stone. Now his opponent has only one move — to take two stones, and then the first player will take the remaining stone.

For $$$N=4$$$, $$$K=3$$$, the second player wins. If the first player takes 1 or 3 stones, the second player will take the remaining 3 or 1. If the first player takes 2 stones, the second player will take 1, and the first player will have no valid moves.