A. From Hero to Zero
implementation; math
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.
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\).