Гра Сюрікен#3122
Бути ніндзя означає проводити багато часу на тренуваннях. Щоб скрасити час між тренуваннями, ніндзя полюбляють грати в ігри зі своїми сюрікенами^1. Однією зі старих улюблених ігор є гра для двох гравців з однією стопкою сюрікенів. По черзі кожен гравець бере кілька сюрікенів зі стопки — щонайменше один, але не більше . Перемагає той, хто забирає останній сюрікен(и). З часом ніндзя розробили переможну стратегію цієї гри та втратили до неї інтерес.
На щастя, один ніндзя запропонував додаткове правило, щоб знову зробити гру цікавою. Це правило полягає в тому, що гравцеві заборонено повторювати попередній хід суперника (тобто брати таку ж кількість сюрікенів, як і попередній гравець). Якщо у стопці залишився лише один сюрікен, а інший гравець щойно взяв один, то гравець, чия черга ходити, не має жодного дозволеного ходу і програє. Чи можете ви допомогти ніндзя визначити, як гравець, який зараз ходить, може виграти в даній ситуації?
________________
^1 Сюрікен — це металева зірка з гострими кутами, яку ніндзя використовують для кидання у ворогів.
Перший рядок містить одне ціле число — кількість тестових випадків. Кожен тестовий випадок має такий формат:
Один рядок з трьома цілими числами , та (1 \leq S \leq 100000, 2 \leq N \leq 100, 1 \leq P \leq N): кількість сюрікенів у стопці, максимальна кількість сюрікенів, яку гравець може взяти за хід, і скільки взяв суперник у попередньому ході.
Для кожного тестового випадку виведіть одне ціле число в окремому рядку: найменшу кількість сюрікенів, яку може взяти гравець, що виконує хід, аби гарантувати перемогу. Якщо виграшного ходу не існує, виведіть 0.
Приклад 1