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.

2
59 3
1000000000000000000 10

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 $ .