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.