Doubloon Game#3129
Being a pirate means spending a lot of time at sea. Sometimes, when there is not much wind, days can pass without any activity. To pass the time between chores, pirates like to play games with coins.
A classic favorite among pirates is a game for two players with a single stack of coins. In turn, each player takes a number of coins from the stack. The number of coins a player takes must be a power of a given integer (, , K^2, and so on). The winner is the player who takes 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 contains a single number: the number of test cases.
Each test case has the following format:
One line with two integers and , where 1 \leq S \leq 10^9 and 1 \leq K \leq 100: the size of the stack and the parameter , respectively.
For each test case, output a single integer on a separate line: the smallest number of coins that the player to move can take to guarantee a win. If there is no winning move, output 0.
Example 1