Gold Coin Game

Being a pirate looks like a wonderful profession, but it has its hardships. One of them is spending long stretches of time on the open sea on days when nothing happens at all. To fight the boredom, pirates know many games played with gold coins.

In one such game, two pirates play over a single pile of gold coins. They take turns one after another. On a turn, for a given integer $K$, a pirate may take a number of coins equal to a power of $K$, i.e. one of $1, K, K^2, K^3, \dots$ (but never more than the coins that remain). The pirate who takes the last coin wins.

Given the number of coins $S$ currently in the pile and the value $K$, determine the minimum number of coins the first pirate must take on the very first turn in order to be guaranteed a win. Both pirates play optimally.

The first line contains the number of test cases.

Each test case consists of a single line with two integers $S$ and $K$. Here $S$ is the number of coins, and $K$ means that on each turn a pirate may take $1, K, K^2, \dots$ coins. ($1 \le S \le 10^9$, $1 \le K \le 100$)

For each test case, print on one line the minimum number of coins the first pirate must take on the first turn in order to win. If the first pirate cannot win no matter how many coins are taken, print $0$.