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 → 26 → 25 → 24 → 8 → 7 → 6 → 2 → 1 → 0.

You are asked to calculate the minimum number of steps to reach 0 from n. 

Input

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}).

Output

For each query print the minimum number of steps to reach 0 from n in single line. 

Example

Input


2
59 3
1000000000000000000 10


Output


8
19

Note

Steps for the first test case are: 59 → 58 → 57 → 19 → 18 → 6 → 2 → 1 → 0.

In the second test case you have to divide n by k 18 times and then decrease n by 1.
# def minSteps(n,k,memo):
    
#     if n in memo:
#         return memo[n]
#     if n==0:
#         return 0
#     if n%k==0:
#         res=minSteps(n/k,k,memo)
#     else:
#         res=minSteps(n-1,k,memo)
#     memo[n]=1+res
#     return memo[n]
#         # return 1 + minSteps(n-1,k)
    
# if __name__=="__main__":
# # Write the main function here
#     # No of tests
#     # global memo
#     t=int(input())
#     for _ in range(t):
        
#         [n,k]=list(map(int,input().split()))
#         memo=[-1 for i in range(n+1)]
#         memo={}
#         print(minSteps(n,k,memo))
        
if __name__=="__main__":
# Write the main function here
    # No of tests
    t=int(input())
    for _ in range(t):
        [n,k]=list(map(int,input().split()))
        count=0
        while n!=0:
            # print(n)
            mod=n%k
            if mod==0:
                n=n//k
                count+=1
            else:
                count=count+mod
                n=n-mod
        print(count)
        