H. A Dance with DS
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game. Alice gives Bob an integer $$$k$$$. Then Bob picks another non-negative integer $$$n$$$ and performs some moves (possibly zero) on $$$n$$$. In one move, he does the following:

  • If $$$k$$$ divides $$$n$$$ (i.e. $$$n\bmod k = 0$$$), then he divides $$$n$$$ by $$$k$$$. Formally, he does $$$n:=\dfrac{n}{k}$$$.
  • Otherwise, he subtracts $$$1$$$ from $$$n$$$. Formally, he does $$$n:=n-1$$$.
If $$$n = 0$$$, he stops performing any further move. Bob wants to play for as long as possible, but he does not want to start with a number too big. Specifically, he doesn't want $$$n$$$ to be bigger than a limit $$$r$$$. Given the limit $$$r$$$, what is the maximum number of moves that can be performed if he chooses $$$n$$$ such that, $$$0 \leq n \leq r$$$?
Input

Input starts with an integer $$$T$$$ ($$$1\leq T\leq 10^5$$$), denoting the number of test cases.

Each of the next $$$T$$$ lines contain two integers $$$r$$$ ($$$0 \leq r \leq 10^{18}$$$) and $$$k$$$ ($$$2 \leq k \leq 10^{18}$$$).

Output

For each test case, you have to print the maximum number of moves that can be performed among all $$$n$$$, such that $$$0 \leq n \leq r$$$.

Example
Input
2
5 2
4 3
Output
4
3
Note

In the first sample, we have $$$r=5$$$. So $$$n$$$ cannot be bigger than $$$5$$$.

  • If $$$n = 0$$$, number of moves $$$=0$$$.
  • If $$$n = 1$$$, number of moves $$$=1$$$ ($$$1 \rightarrow 0$$$).
  • If $$$n = 2$$$, number of moves $$$=2$$$ ($$$2 \rightarrow 1 \rightarrow 0$$$).
  • If $$$n = 3$$$, number of moves $$$=3$$$ ($$$3 \rightarrow 2 \rightarrow 1 \rightarrow 0$$$).
  • If $$$n = 4$$$, number of moves $$$=3$$$ ($$$4 \rightarrow 2 \rightarrow 1 \rightarrow 0$$$).
  • If $$$n = 5$$$, number of moves $$$=4$$$ ($$$5 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 0$$$).

If we choose $$$n = 5$$$, we get the maximum number of moves $$$=4$$$.