Игра Сюрикен
Быть ниндзя означает проводить много времени на тренировках. Чтобы скоротать время между тренировками, ниндзя любят играть в игры с сюрикэнами^1. Одна из их старых любимых игр — это игра для двух игроков с одной стопкой сюрикэнов. Игроки по очереди берут некоторое количество сюрикэнов из стопки: как минимум один, но не более N. Побеждает тот, кто возьмет последний сюрикэн(ы). Со временем ниндзя выяснили, какую стратегию нужно использовать, чтобы выиграть, и потеряли интерес к игре.
К счастью, один из ниндзя придумал дополнительное правило, которое, возможно, сделает игру снова интересной. Это правило заключается в том, что игроку запрещено повторять последний ход своего соперника, то есть брать такое же количество сюрикэнов, как и его соперник в предыдущем ходе. Если в стопке остался только один сюрикэн, и предыдущий игрок взял один, у следующего игрока нет допустимого хода, и он проигрывает. Можете ли вы помочь ниндзя определить, как игрок, который должен ходить, может выиграть в данной игровой ситуации?
________________
^1 - Сюрикэн — это металлическая звезда с острыми углами, которую ниндзя используют для метания в врагов.
Входные данные
Первая строка ввода содержит одно число: количество тестов, которые следуют. Каждый тест имеет следующий формат:
Одна строка с тремя целыми числами S, N и P, удовлетворяющими условиям 1 ≤ S ≤ 100000, 2 ≤ N ≤ 100 и 1 ≤ P ≤ N: количество сюрикэнов в стопке, максимальное количество сюрикэнов, которое игрок может взять из стопки, и последний ход другого игрока соответственно.
Выходные данные
Для каждого теста во входных данных вывод должен содержать одно целое число в отдельной строке: наименьшее количество сюрикэнов, которое игрок, который должен ходить, может взять, чтобы обеспечить победу. Если выигрышного хода нет, вывод должен быть 0.