e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Matches for children are not toys!

Matches for children are not toys!

prb1005

There are n matches on the table. Two players take turns. A player may take no more than m matches, but not less than one. Player who takes the last match is a winner.

Who will win in the regular game - the first or second player?

Input

The first line contains the number of test cases t (1t100). Each of the next t lines contains the number of matches n in the heap and the maximum number of matches m that allowed to take in one move. It is known that 1n, m2 * 109.

Output

Print a sequence of t ones and twos: 1 - if the first player wins and 2 - if the second player wins.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2
7 3
8 3
Output example #1
12