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** * `10`

.^{9}

#### 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