B'You are given an integer n and an integer k . In one step you can do one of the following moves: 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 <= t <= 100 ) -- the number of queries. The only line of each query contains two integers n and k ( 1 <= n <= 10^{18} , 2 <= k <= 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 . '...