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