From Hero to Zero
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
You are given an integer $n$ and an integer $k$.
In one step you can do one of the following moves:
- decrease $n$ by $1$;
- divide $n$ by $k$ if $n$ is divisible by $k$.
For example, if $n = 27$ and $k = 3$ you can do the following steps: $27 \rightarrow 26 \rightarrow 25 \rightarrow 24 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$.
You are asked to calculate the minimum number of steps to reach $0$ from $n$.
The first line contains one integer $t$ ($1 \le t \le 100$) — the number of queries.
The only line of each query contains two integers $n$ and $k$ ($1 \le n \le 10^{18}$, $2 \le k \le 10^{18}$).
For each query print the minimum number of steps to reach $0$ from $n$ in single line.
Input
The first line contains one integer $t$ ($1 \le t \le 100$) — the number of queries.
The only line of each query contains two integers $n$ and $k$ ($1 \le n \le 10^{18}$, $2 \le k \le 10^{18}$).
Output
For each query print the minimum number of steps to reach $0$ from $n$ in single line.
2
59 3
1000000000000000000 10
8
19
Note
Steps for the first test case are: $59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$.
In the second test case you have to divide $n$ by $k$ $18$ times and then decrease $n$ by $1$.
20240326集训
- Status
- Done
- Rule
- IOI
- Problem
- 7
- Start at
- 2024-3-26 19:00
- End at
- 2024-3-26 21:00
- Duration
- 2 hour(s)
- Host
-
SamuelXuch
- Partic.
- 14