A Dance with DS
Description
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$.
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}$).
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$.
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$.
2
5 2
4 3
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$.