Shuriken Game

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 (a shuriken is a metal star with sharp corners that ninjas throw at enemies).

This is a game for two players featuring a single stack of shurikens. The players take turns. On a turn, a player removes some shurikens from the stack: at least $1$ and at most $N$. The player who takes the last shuriken(s) wins.

The basic game was quickly solved, so an extra rule was added to make it interesting again: a player may not take the same number of shurikens the opponent just took (you cannot copy your opponent's last move). If the stack holds exactly $1$ shuriken and the opponent has just taken $1$, the player to move has no legal move and loses.

For a given situation, determine how the player to move can win.

The first line contains the number of test cases $T$. Each test case has the following format:

• One line with three integers $S$, $N$, and $P$ ($1 \le S \le 100000$, $2 \le N \le 100$, $1 \le P \le N$): the number of shurikens in the stack, the maximum number of shurikens a player may take, and the number the opponent took on the last move, respectively.

For each test case, print one integer on its own line: the smallest number of shurikens the player to move can take to secure the win. If there is no winning move, print $0$.