A. From Hero to Zerotime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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. InputThe 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}).OutputFor each query print the minimum number of steps to reach 0 from n in single line. ExampleInput
2
59 3
1000000000000000000 10
Output
8
19
NoteSteps 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.
2
59 3
1000000000000000000 10

8 19 
['implementation', 'math', '*900']