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$. 


-----Input-----

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


-----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 \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$.

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n, k = list(map(int, input().split()))
	ans = 0
	while n != 0:
		if n % k == 0:
			ans += 1
			n //= k
		else:
			ans += n % k
			n -= n % k
	print(ans)


t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    ans = 0
    while n > 0:
        if n % k == 0:
            n//=k
            ans += 1
        else:
            ans += n % k
            n -= n % k
    print(ans)

for TT in range(1, int(input()) + 1):
    n, k = map(int, input().split())
    res = 0
    while n:
        if n % k:
            res += n % k
            n -= n % k
        if n:
            n //= k
            res += 1
    print(res)

#JMD
#Nagendra Jha-4096

 
import sys
import math

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('W:/Competitive Programming/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###
def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans
 
 
##### Main ####
t=int(input())
for tt in range(t):
    #n=int(input())
    n,k= map(int, sys.stdin.readline().split(' '))
    s=0
    while (n!=0):
        rem=n%k
        s+=rem
        n-=rem
        if(n>0):
            s+=1
        n//=k
    print(s)
    #a=list(map(int,sys.stdin.readline().split(' ')))
    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()

for _ in range(int(input())):
    n,k=list(map(int,input().split()))
    ans=0
    while(n>0):
        if(n%k==0):
            n//=k
            ans+=1
        else:
            ans+=n%k
            n-=n%k
    print(ans)


n=int(input())
for i in range(n):
    a,b=list(map(int,input().split()))
    ans=0
    while(a>0):
        if(a%b==0):
            a//=b
            ans+=1
        else:
            ans+=(a-(a//b)*b)
            a=(a//b)*b
    print(int(ans))
           


t = int(input())
for i in range(t):
    ans = 0
    n, k = list(map(int, input().split()))
    while (n != 0):
        if (n % k == 0):
            n //= k
            ans += 1
        else:
            ans += n % k
            n -= n % k
    print(ans)

t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    c = 0
    while n > 0:
        if n % k == 0:
            n //= k
            c += 1
        else:
            m = n % k
            n -= m
            c += m
    print(c)


for _ in range(int(input())):
    n,k=map(int,input().split())
    step=0
    while(n>0):
        if(n%k!=0):
            step+=(n%k)
            n-=(n%k)
        else:
            while(n%k==0):
                n//=k
                step+=1
    print(step)

ii = lambda: int(input())
mi = lambda: list(map(int, input().split()))
li = lambda: list(mi())

for _ in range(ii()):
    n, k = mi()
    ans = 0
    while n:
        if n % k:
            ans += n % k
            n -= n % k
        else:
            ans += 1
            n //= k
    print(ans)


t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    cnt = 0
    while n != 0:
        if n % k == 0:
            n //= k
            cnt += 1
        else:
            cnt += n % k
            n = n - n % k
    print(cnt)


t = int(input())
for i in range(0, t):
    n, k = map(int, input().split())
    c = 0
    while (n != 0):
        if (n % k != 0):
            c += n%k
            n = n - n%k
        else:
            c += 1
            n = n // k
    print(c)

t = int(input())
for i in range(t):
	n, k = map(int, input().split())
	cnt = 0
	while n != 0:
		cnt += n % k
		n //= k
		cnt += 1
	print(cnt - 1)

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    if k == 1:
        print(n)
    else:
        ans = 0
        while n != 0:
            if n % k == 0:
                n //= k
                ans += 1
            else:
                q = n - n // k * k
                ans += q
                n = n // k * k
        print(ans)


t = int(input())

for _ in range(t):
	n, k = list(map(int, input().split()))

	count = 0

	while n:
		if n%k==0:
			n //=k
			count += 1
		else:
			mod = n%k
			n -= mod
			count += mod

	print(count)



from bisect import *
from collections import *
from itertools import *
import functools
import sys
from math import *
from decimal import *
from copy import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 10**5+10
MOD = 10**9+7
def isprime(n):
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2: 
        return True    
    if not n & 1: 
        return False
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

def mhd(a,b):
    return abs(a[0]-b[0])+abs(b[1]-a[1])

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def dis(x,y):
    a = y[0]-x[0]
    b = x[1]-y[1]
    return (a*a+b*b)**0.5

def lgcd(a):
    g = a[0]
    for i in range(1,len(a)):
        g = math.gcd(g,a[i])
    return g

def ms(a):
    msf = -MAX
    meh = 0
    st = en = be = 0
    for i in range(len(a)):
        meh+=a[i]
        if msf<meh:
            msf = meh
            st = be
            en = i
        if meh<0:
            meh = 0
            be = i+1
    return msf,st,en

def flush():
    return sys.stdout.flush()

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
for _ in range(int(input())):
    n,k = arrIN()
    ans = 0
    while 1:
        if n%k==0:
            n//=k
            ans+=1
        else:
            x = n%k
            ans+=x
            n-=x
        if n==0:
            print(ans)
            break



t = int(input())

def solve(n, k):
    acc = 0
    while n > 0:
        if n % k == 0:
            acc += 1
            n //= k
        else:
            acc += n % k
            n -= n % k
    return acc

for query in range(t):
    n, k = list(map(int, input().strip().split()))
    print(solve(n, k))


t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    summ = 0
    while n > 0:
        if n % k == 0:
            summ += 1
            n //= k
        else:
            summ += n % k
            n = n - n % k
    print(summ)

t = int(input())

for i in range(t):
    n, k = map(int, input().split())
    res = 0
    while n > 0:
        res += n % k
        n -= n % k
        if n > 0:
            n = n//k
            res += 1
    print(res)

t = int(input())
for _ in range(t):
    n,k=map(int, input().split())
    ans = 0
    while n != 0:
        if n % k == 0:
            n //= k
            ans += 1
        else:
            ans += n % k
            n -= n % k
    print(ans)

def main():
    t = int(input())
    for i in range(t):
        steps = 0
        n,k = list(map(int,input().split()))
        while n != 0:
            if n%k == 0:
                n = n//k
                steps += 1
            else:
                steps += n%k
                n -= n%k

        print(steps)


main()


t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    count = 0
    while n != 0:
        if n % k == 0:
            n//=k
            count += 1
        else:
            count += n%k
            n -= n%k
    print(count)

q=int(input())
for i in range(q):
    n,k=[int(x) for x in input().split()]
    counter=0
    while n!=0:
        x=n%k
        n-=x
        counter+=x+1
        n//=k
    print(counter-1)


from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))


q=nn()


for _ in range(q):
	n,k=mi()
	moves=0
	while n>=k:
		moves+=n%k+1

		n=n//k
		#print(n)
	moves+=n
	print(moves)