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.
import math as mt 
import sys,string,bisect
input=sys.stdin.readline
from collections import deque
L=lambda : list(map(int,input().split()))
Ls=lambda : list(input().split())
M=lambda : map(int,input().split())
I=lambda :int(input())
def initializeDiffArray( A): 
    n = len(A) 
    D = [0 for i in range(0 , n + 1)] 
  
    D[0] = A[0]; D[n] = 0
      
    for i in range(1, n ): 
        D[i] = A[i] - A[i - 1] 
    return D 
  
def update(D, l, r, x): 
  
    D[l] += x 
    D[r + 1] -= x

def printArray(A, D):   
    for i in range(0 , len(A)): 
        if (i == 0): 
            A[i] = D[i] 
        else: 
            A[i] = D[i] + A[i - 1]

  
MAXN = 100001
  
# stores smallest prime factor for 
# every number 
spf = [0 for i in range(MAXN)] 
  
# Calculating SPF (Smallest Prime Factor)  
# for every number till MAXN. 
# Time Complexity : O(nloglogn) 
def sieve(): 
    spf[1] = 1
    for i in range(2, MAXN): 
          
        # marking smallest prime factor  
        # for every number to be itself. 
        spf[i] = i 
  
    # separately marking spf for  
    # every even number as 2 
    for i in range(4, MAXN, 2): 
        spf[i] = 2
  
    for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
          
        # checking if i is prime 
        if (spf[i] == i): 
              
            # marking SPF for all numbers 
            # divisible by i 
            for j in range(i * i, MAXN, i):  
                  
                # marking spf[j] if it is  
                # not previously marked 
                if (spf[j] == j): 
                    spf[j] = i 
  
# A O(log n) function returning prime  
# factorization by dividing by smallest  
# prime factor at every step 
def getFactorization(x): 
    ret = list() 
    while (x != 1): 
        ret.append(spf[x]) 
        x = x // spf[x] 
  
    return ret

n=I()
for i in range(n):
    a,b=M()
    c=0
    while(a!=0):
        if(a%b==0):
            a=a//b
            c+=1
        else:
            c+=a%b
            a=a-(a%b)
    print(c)
    
