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