Children of a match is not a toy!
On the table there are N matches. They play two, take turns. A player may take no more than M matches, but not less than one. Took away the last match wins.
Who will win in the regular game - the first or second player?
Specifications
Input
In the first line is the number of T - the number of test cases. In the following T lines are two numbers, separated by a space: N - number of matches in the pile and M - the maximum allowed for the capture of one move.
1 ≤ T ≤ 100, 1 ≤ N, M ≤ 2·109.
Output
In a single line display a sequence of ones and twos T, 1 - for the case if the right wins the first game and, respectively, 2 - if the player wins the second.
Problem information
Time Limit: 1 secondsMemory Limit: 64 MB
Balls for the passed test: 10
Complexity: 22% 183/234
Classes: Number theory, Simple mathematics, Beginners
Example
Example input2 7 3 8 3 |
Example output12 |
| ← Çàáàâíàÿ èãðà | Problems | Simple arithmetic → |