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