Matches for children are not toys!

Matches for children are not toys!


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?


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.


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
7 3
8 3
Output example #1