eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Doubloon Game

Doubloon Game

Лимит времени 1 секунда
Лимит использования памяти 32 MiB

Being a pirate means spending a lot of time at sea. Sometimes, when there is not much wind, days can pass by without any activity. To pass the time between chores, pirates like to play games with coins.

An old favorite of the pirates is a game for two players featuring one stack of coins. In turn, each player takes a number of coins from the stack. The number of coins that a player takes must be a power of a given integer K (1, K, K^2, etcetera). The winner is the player to take the last coin(s).

Can you help the pirates figure out how the player to move can win in a given game situation?

Входные данные

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:

  • One line with two integers S and K, satisfying 1S10^9 and 1K100: the size of the stack and the parameter K, respectively.

Выходные данные

For every test case in the input, the output should contain one integer on a single line: the smallest number of coins that the player to move can take in order to secure the win. If there is no winning move, the output should be 0.

Пример

Входные данные #1
5
5 1
3 2
8 2
50 3
100 10
Выходные данные #1
1
0
2
0
1