Problems
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?
Input
The first line contains the number of test cases t (1 ≤ t ≤ 100). 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 1 ≤ n, m ≤ 2 * 109
.
Output
Print a sequence of t ones and twos: 1 - if the first player wins and 2 - if the second player wins.
Input example #1
2 7 3 8 3
Output example #1
12