From Hero to Zero
题意翻译
给整数 $n,k$,每次你可以做如下两个操作之一
- 将 $n$ 减 $1$
- 将 $n$ 除以 $k$ (前提:$n$ 是 $k$ 的倍数)
试求让 $n$ 变为 $0$ 的最小操作次数。
题目描述
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.
输入输出样例
输入样例 #1
2
59 3
1000000000000000000 10
输出样例 #1
8
19
说明
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 $ .