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