Shuriken Game#3122
Being a ninja means spending a lot of time training. To pass the time between training sessions, ninjas like to play games with their shurikens^1. An old favorite of the ninjas is a game for two players with one stack of shurikens. In turn, each player takes a number of shurikens from the stack — at least one, but at most . The winner is the player who takes the last shuriken(s). Over time, ninjas figured out the winning strategy for this game and lost interest.
Fortunately, one ninja introduced an additional rule to make the game interesting again. This rule states that a player is not allowed to copy the opponent's last move (i.e., to take the same number of shurikens as the previous player). If the stack contains only one shuriken and the other player just took one, the player whose turn it is has no legal move and loses. Can you help the ninjas determine how the player to move can win in a given situation?
________________
^1 A shuriken is a metal star with sharp corners which ninjas use to throw at enemies.
The first line contains a single integer — the number of test cases. Each test case has the following format:
One line with three integers , and (1 \leq S \leq 100000, 2 \leq N \leq 100, 1 \leq P \leq N): the number of shurikens in the stack, the maximum number of shurikens a player may take from the stack, and the last move made by the other player.
For each test case, output a single integer on a separate line: the smallest number of shurikens the player to move can take to guarantee a win. If there is no winning move, output 0.
Example 1