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: EASY
Tags: Mathematics

Implementation

Starter code:

Solutions:
def answer_query(n, k):
	r = 0
	while n > 0:
		r += n % k
		n -= n % k
		while n % k == 0 and n > 0:
			r += 1
			n //= k
	print(r)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	answer_query(n, k)


import sys
import math
from functools import reduce
n = int(input())
for x in range(n):
	(n, k) = map(int, sys.stdin.readline().split())
	counter = 0
	while n != 0:
		if n % k == 0:
			n //= k
			counter += 1
		else:
			t = n % k
			n -= t
			counter += t
	print(counter)


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


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 - n % k
		else:
			step += 1
			n = n // k
	print(step)


t = int(input())
for te in range(0, t):
	(n, k) = [int(x) for x in input().split()]
	c = int(0)
	while n != 0:
		c += n % k
		n = n - n % k
		if n == 0:
			break
		if n % k == 0:
			n = n // k
			c += 1
			if n == 0:
				break
	print(c)


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)


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


def int2base(n, b):
	if n == 0:
		return [0]
	digits = []
	while n:
		digits.append(int(n % b))
		n //= b
	return digits[::-1]
t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	count = 0
	base_k = int2base(n, k)
	count = count + len(base_k)
	for i in base_k:
		count = count + i
	print(count - 1)


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


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


from sys import stdin
n = int(stdin.readline())
for _ in range(n):
	(n, k) = map(int, stdin.readline().split())
	cnt = -1
	while n > 0:
		cnt += n % k
		n = n // k
		cnt += 1
	print(int(cnt))


from sys import stdin, stdout

def main():
	(mp, read, write) = (map, stdin.readline, stdout.write)
	t = int(read())
	for _ in range(t):
		(N, K) = map(int, read().split())
		write(str(evaluate(N, K)) + '\n')

def evaluate(N, K):
	count = 0
	while N:
		if N % K == 0:
			count += 1
			N //= K
		else:
			count += N % K
			N = N - N % K
	return count
main()


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


tests = int(input())
for each in range(tests):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	count = 0
	while n != 0:
		if n % k == 0:
			n = n // k
			count += 1
		else:
			rest = n % k
			n -= rest
			count += rest
	print(int(count))


def mainq():
	t = int(input())
	for x in range(0, t):
		(a, b) = input().split()
		a = int(a)
		flag = 1
		b = int(b)
		count = 0
		while a > 0:
			count = count + a % b
			a = a - a % b
			if a:
				count = count + 1
			a = a // b
		print(int(count))
mainq()


from sys import stdin, stdout
import math
T = int(stdin.readline())
for __ in range(T):
	(N, K) = map(int, stdin.readline().split())
	count = 0
	while N:
		if N % K == 0:
			N = N // K
			count += 1
		else:
			count += N - K * (N // K)
			N = K * (N // K)
	stdout.write(str(count) + '\n')


test = int(input())
while test:
	test -= 1
	t = list(map(int, input().split(' ')))
	n = t[0]
	k = t[1]
	c = 0
	while n != 0:
		if n % k == 0:
			n = n // k
			c = c + 1
		else:
			t = n % k
			n -= t
			c = c + t
		if n < k:
			c = c + n
			break
	print(c)


cases = int(input())
while cases > 0:
	cases -= 1
	steps = 0
	line = input().split(' ')
	a = int(line[0])
	b = int(line[1])
	while a > 0:
		if a % b == 0:
			a //= b
			steps += 1
		else:
			steps += int(a % b)
			a -= int(a % b)
	print(steps)


T = int(input())
for t in range(0, T):
	A = list(map(int, input().strip().split()))
	a = A[0]
	b = A[1]
	c = -1
	while a != 0:
		c = c + a % b + 1
		a = a // b
	print(c)


import sys

def result(n, k):
	if n < k:
		return n
	else:
		(i, j) = divmod(n, k)
		return result(i, k) + j + 1
t = int(input())
for i in range(t):
	(n, k) = input().split(' ')
	(n, k) = (int(n), int(k))
	sys.stdout.write(str(result(n, k)) + '\n')


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


n = int(input())
k = []

def z(a, b):
	rez = 0
	while a != 0:
		if a % b == 0:
			a //= b
			rez += 1
		else:
			rez += a % b
			a -= a % b
	return rez
for i in range(n):
	a = input().split()
	k.append([int(a[0]), int(a[1])])
for i in range(n):
	print(z(k[i][0], k[i][1]))


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


for test in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	step = 0
	while n > 0:
		t = n % k
		if t == 0:
			n //= k
			step += 1
		else:
			n -= t
			step += t
	print(step)


t = int(input())

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


from sys import stdin, stdout

def func(n, k):
	ans = 0
	while n != 0:
		rem = n % k
		if rem == 0:
			ans += 1
			n = n // k
		else:
			ans += int(rem)
			n -= int(rem)
	return str(ans)
n = int(stdin.readline())
for _ in range(n):
	(n, k) = stdin.readline().split()
	n = int(n)
	k = int(k)
	stdout.write(func(n, k))
	print()


from sys import stdin
import math
from collections import defaultdict, deque
import bisect
I = stdin.readline
for _ in range(int(I())):
	(n, m) = map(int, I().split())
	ans = 0
	while n != 0:
		rem = n % m
		if rem != 0:
			ans += rem
			n -= rem
		else:
			ans += 1
			n //= m
	print(ans)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	count = 0
	while x > 0:
		count += x % y + 1
		x = x // y
	print(count - 1)


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


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


test_cases = int(input())
data = []
while test_cases > 0:
	data.append(list(map(int, input().split())))
	test_cases -= 1
for i in range(0, len(data)):
	step = 0
	n = data[i][0]
	k = data[i][1]
	while n > 0:
		if k > n:
			step += n
			n = 0
		elif n % k == 0:
			n = n // k
			step += 1
		else:
			step += n % k
			n -= n % k
	print(int(step))


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
	moves += n
	print(moves)


tc = int(input())
for i in range(tc):
	(a, b) = input().split()
	num = int(a)
	div = int(b)
	count = 0
	while num > 0:
		if num % div == 0:
			num = num // div
			count = count + 1
		else:
			count = count + num % div
			num = num - num % div
	print(count)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	i = 0
	while a != 0:
		if a % b == 0:
			a //= b
			i += 1
		else:
			x = a % b
			i += x
			a -= x
	print(i)


import sys

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def next(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = self.next_line()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_line(self):
		return sys.stdin.readline().split()

	def next_ints(self):
		return [int(x) for x in sys.stdin.readline().split()]

	def next_int(self):
		return int(self.next())

	def solve(self):
		ca = self.next_int()
		for _ in range(ca):
			(n, k) = self.next_ints()
			stp = 0
			while n > 0:
				if n % k == 0:
					n //= k
					stp += 1
				else:
					stp += n % k
					n -= n % k
			print(stp)
Main().solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	res = 0
	while n > 0:
		(div, mod) = divmod(n, k)
		if div > 0:
			res += mod + 1
			n = div
		else:
			res += mod
			n = div
			break
	print(res)


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


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


import math
n = int(input())
for i in range(0, n):
	ln = [int(j) for j in input().split(' ')]
	n = ln[0]
	k = ln[1]
	s = 0
	j = 1
	while n > 0:
		on = n
		n -= n % k
		s += on - n + 1
		n = n // k
	s -= 1
	print(s)


import math
alph = 'abcdefghijklmnopqrstuvwxyz'
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if k > n:
		print(n)
	else:
		E = 0
		while n != 0:
			if n % k == 0:
				n //= k
				E += 1
			else:
				E += n % k
				n -= n % k
		print(E)


t = int(input())
for i in range(0, t):
	(n, k) = [int(x) for x in input().split()]
	count = int(0)
	while n > 0:
		m = n % k
		n -= m
		count += m
		n = n // k
		count += 1
	print(count - 1)


def func(n, k):
	if k == 1:
		return n
	count = 0
	while n > 0:
		while n % k == 0:
			n = n // k
			count += 1
		else:
			count += n % k
			n = n - n % k
	return count
t = int(input())
for i in range(t):
	a = [int(i) for i in input().split()]
	n = a[0]
	k = a[1]
	print(func(n, k))


t = int(input())
for i in range(t):
	nk = input().split(' ')
	n = int(nk[0])
	k = int(nk[1])
	ans = 0
	while n >= k:
		(q, r) = (n // k, n % k)
		n = q
		ans += r + 1
	print(ans + n)


t = int(input())

def base(n, k):
	if n == 0:
		return 0
	return n % k + base(n // k, k) + 1
for u in range(t):
	(n, k) = map(int, input().split())
	print(base(n, k) - 1)


t = int(input())
for _ in range(t):
	(a, b) = list(map(int, input().split()))
	result = 0
	while a > 0:
		if a % b == 0:
			a //= b
			result += 1
		else:
			temp = a % b
			a -= temp
			result += temp
	print(result)


t = int(input())
for i2 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)


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


import math
import decimal
D = decimal.Decimal
t = int(input())
for x in range(t):
	l1 = [int(x) for x in input().split()]
	n = l1[0]
	k = l1[1]
	nearest = n
	ans = 0
	while nearest >= 1:
		ans += nearest % k
		nearest -= nearest % k
		nearest = int(D(nearest // k))
		ans += 1
	print(ans - 1)


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


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


a = int(input())
for value in range(a):
	startVal = input().split(' ')
	startVal[0] = int(startVal[0])
	startVal[1] = int(startVal[1])
	counter = 0
	while True:
		if startVal[0] == 0:
			break
		if startVal[0] % startVal[1] == 0:
			startVal[0] = startVal[0] // startVal[1]
			counter += 1
		else:
			mod = int(startVal[0] % startVal[1])
			startVal[0] -= mod
			counter += mod
	print(counter)


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


def main():
	test_cases = int(input())
	pairs = []
	while test_cases > 0:
		pairs.append(input().split(' '))
		test_cases -= 1
	for pair in pairs:
		n = int(pair[0])
		k = int(pair[1])
		steps = 0
		if k == 1:
			steps = n
		else:
			while n > 0:
				if n % k == 0:
					n = n // k
					steps += 1
				else:
					steps += n % k
					n -= n % k
		print(steps)
main()


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)


queries = int(input())
j = 0
for i in range(queries):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	n1 = n
	while n != 0:
		if k > n1:
			j = n
			n = 0
		elif n % k == 0:
			n = int(n // k)
			j += 1
		else:
			x = int(n // k)
			y = x * k
			j += n - y
			n = y
	print(j)
	j = 0


def result(n, k):
	if n < k:
		return n
	else:
		(i, j) = divmod(n, k)
		return result(i, k) + j + 1
t = int(input())
for i in range(t):
	(n, k) = input().split(' ')
	(n, k) = (int(n), int(k))
	print(str(result(n, k)))


def solution():
	global n, k
	for i in range(int(input())):
		answer = 0
		(n, k) = map(int, input().split())
		while n:
			helpVar = n % k
			if helpVar:
				n -= helpVar
				answer += helpVar
			else:
				n //= k
				answer += 1
		print(answer)
solution()


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


t = int(input())
for _ in range(t):
	s = input().split(' ')
	n = int(s[0])
	k = int(s[1])
	count = 0
	while n >= k and n != 1:
		r = n % k
		count = count + r
		n = n - r
		n = n // k
		count = count + 1
	count = count + n
	print(int(count))


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


from sys import stdin
lines = int(stdin.readline())
while lines > 0:
	(num, divi) = stdin.readline().split()
	num = int(num)
	divi = int(divi)
	count = 0
	while num > 0:
		if num % divi == 0:
			num = num // divi
			count += 1
		else:
			count += num % divi
			num = num - num % divi
	print(int(count))
	lines -= 1


t = int(input())
c = []
while t:
	(n, k) = map(int, input().split())
	cnt = 0
	while n:
		if n == 1:
			cnt += 1
			n -= 1
		elif n % k:
			cnt += n % k
			n -= n % k
		else:
			cnt += 1
			n = n // k
	c.append(cnt)
	t -= 1
for i in c:
	print(int(i))


import sys
numtest = int(sys.stdin.readline())
for _ in range(numtest):
	step = 0
	(n, k) = [int(i) for i in sys.stdin.readline().strip().split(' ')]
	while n > 0:
		if n >= k:
			step += n % k + 1
		else:
			step += n
		n = n // k
	print(step)


t = int(input())
for x in range(t):
	(n, k) = [int(x) for x in input().split()]
	steps = 0
	while n != 0:
		if n % k != 0:
			steps += n % k
			n -= n % k
		else:
			steps += 1
			n //= k
	print(steps)


for tc in range(int(input())):
	(x, y) = map(int, input().split())
	ans = 0
	while x:
		ans += x % y + 1
		x = x // y
	print(ans - 1)


from sys import stdin, stdout
from collections import Counter

def ai():
	return list(map(int, stdin.readline().split()))

def ei():
	return map(int, stdin.readline().split())

def ip():
	return int(stdin.readline().strip())

def op(ans):
	return stdout.write(str(ans) + '\n')
import time
t = ip()
for i in range(t):
	(n, k) = ei()
	c = 0
	while n != 0:
		if n % k == 0:
			n //= k
			c += 1
		else:
			c += n % k + 1
			n //= k
	op(c - 1)


n = int(input())
for i in range(0, n):
	p = input().rstrip().split(' ')
	n = int(p[0])
	k = int(p[1])
	GG = 0
	if 1:
		while n != 0:
			if n % k == 0:
				n = n // k
				GG += 1
			else:
				G = n // k
				A = G * k
				GG += n - A
				n = A
		print(GG)


ii = lambda : int(input())
mi = lambda : 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)


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


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


def solve(n, k):
	count = 0
	while n != 0:
		m = n % k
		if m == 0:
			n = n // k
			count += 1
		else:
			n -= m
			count += m
	return int(count)

def test():
	assert solve(999999999999999999, 100000000000000000) == 100000000000000009
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	print(solve(n, k))


for x in range(int(input())):
	(n, k) = list(map(int, input().split()))
	cout = 0
	while n > 0:
		if n < k:
			cout += n
			break
		elif n % k == 0:
			n = n // k
			cout += 1
		else:
			cout += n % k
			n = n - n % k
	print(cout)


t = int(input())
ts = []
for i in range(t):
	c = 0
	(n, k) = (int(j) for j in input().split())
	while n > 0:
		c += n % k + 1
		n = n // k
	print(c - 1)


q = int(input())
for _ in range(q):
	(n, k) = list(map(int, input().split()))
	counter = 0
	for _ in range(max(n, k)):
		z = n % k
		if z == 0:
			n = n // k
			counter += 1
		elif n // k == 0:
			counter += n
			n = 0
			break
		else:
			n -= z
			counter += z
		if n == 0:
			break
	print(counter)


def main():
	(n, k) = map(int, input().split())
	cnt = 0
	while n > 0:
		if n % k:
			cnt += n % k
			n = n - n % k
		else:
			n = n // k
			cnt += 1
	print(cnt)
	return

def test():
	t = int(input())
	while t:
		main()
		t -= 1
test()


x = int(input())
for __ in range(x):
	(a, k) = map(int, input().split())
	c = 0
	while a != 0:
		if a % k == 0:
			a = a // k
			c += 1
		else:
			b = a % k
			a -= b
			c += b
	print(c)


num_queries = int(input())
res = []
for _ in range(num_queries):
	(n, k) = map(int, input().split())
	num_steps = 0
	while n != 0:
		num_steps += n % k + 1
		n //= k
	res.append(num_steps - 1)
[print(i) for i in res]


for i in range(int(input())):
	t = 0
	x = list(map(int, input().split()))
	while x[0] != 0:
		if x[0] % x[1] == 0:
			x[0] = x[0] // x[1]
			t = t + 1
		else:
			r = x[0] % x[1]
			x[0] = x[0] - r
			t = t + r
	print(t)


R = ''
for i in range(int(input())):
	(N, K) = map(int, input().split())
	C = 0
	while N != 0:
		C += N % K + 1
		N = N // K
	R += str(C - 1) + '\n'
print(R)


a = []
number = int(input())
for i in range(number):
	a.append(list(map(int, input().split())))
for s in a:
	(n, k) = s
	ans = 0
	while n > 0:
		if n < k:
			ans += n
			break
		ans += n % k + 1
		n = n // k
	print(ans)


def scand():
	return int(input())

def scana():
	return [int(x) for x in input().split()]
t = scand()

def solve():
	(n, k) = scana()
	ret = 0
	while n > 0:
		if not n % k:
			n //= k
			ret += 1
		else:
			ret += n % k
			n -= n % k
	return ret
for i in range(t):
	print(solve())


a = int(input())
for i in range(a):
	(b, c) = map(int, input().split())
	q = 0
	while b != 0:
		aux = b // c
		q += b - aux * c
		b = aux
		if aux > 0:
			q += 1
	print(q)


n = int(input())
for _ in range(n):
	(a, b) = list(map(int, input().split()))
	c = 0
	while a >= b:
		c += a % b + 1
		a = a // b
	c += a
	print(c)


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k > n:
		print(n)
	elif n == k:
		print(2)
	else:
		count = 0
		while n > 0:
			foo = n % k
			if foo == 0:
				n = n // k
				count += 1
			else:
				n = n - foo
				count += foo
			if n == 0:
				break
		print(count)


for _ in ' ' * int(input()):
	(a, b) = map(int, input().split())
	s = 0
	while a >= b:
		if not a % b:
			a = a // b
			s += 1
		else:
			f = a % b
			a -= f
			s += f
	print(a + s)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = 0
	while n > 0:
		if n % k == 0:
			n //= k
			a += 1
		else:
			a += n % k
			n -= n % k
	print(a)


class WayToZero:

	def __init__(self, n):
		self.n = n
		self.data = []
		self.output = []
		self.read()

	def read(self):
		for i in range(self.n):
			temp = [int(x) for x in input().split(' ')]
			self.data.append(temp)

	@staticmethod
	def calculate(x, k):
		result = -1
		while x != 0:
			modulo = x % k
			x //= k
			result += 1 + modulo
		return result

	def calculate_all(self):
		for i in range(self.n):
			self.output.append(self.calculate(self.data[i][0], self.data[i][1]))

	def __repr__(self):
		return '\n'.join([str(x) for x in self.output])

def main():
	way = WayToZero(int(input()))
	way.calculate_all()
	print(way)
main()


N = int(input())
for input_line in [input() for n in range(N)]:
	(n, k) = map(int, input_line.split())
	num = 0
	while True:
		if n % k == 0:
			n //= k
			num += 1
		else:
			num += n % k
			n -= n % k
		if n == 0:
			break
	print(num)


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


import sys
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	(n, k) = list(map(int, sys.stdin.readline().strip().split()))
	c = 0
	if k == 1:
		c = n
		n = 0
	while n > 0:
		if n % k == 0:
			n = n // k
			c = c + 1
		else:
			c = c + n % k
			n = k * (n // k)
	print(c)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	noOfMoves = 0
	while n != 0:
		rem = n % k
		if rem != 0:
			noOfMoves += rem
			n = n - rem
		else:
			noOfMoves += 1
			n = n // k
	print(noOfMoves)


import os
from io import BytesIO, StringIO

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

def array_of(f, *dim):
	return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = input_as_list()
		(j, s) = (0, 0)
		while n > 0:
			s += n % k
			j += 1
			n //= k
		print(j + s - 1)
main()


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


t = int(input())
for i in range(t):
	l = list(map(int, input().split(' ')))
	n = l[0]
	k = l[1]
	count = 0
	while n > 0:
		count += n % k + 1
		n = n // k
	print(count - 1)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	res = 0
	while a != 0:
		if a % b == 0:
			a //= b
			res += 1
		else:
			res += a % b
			a -= a % b
	print(res)


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


import sys
input = sys.stdin.readline
for _ in range(int(input().rstrip())):
	(n, k) = map(int, input().rstrip().split())
	result = 0
	while n != 0:
		if n % k == 0:
			n //= k
			result += 1
		else:
			result += n % k
			n -= n % k
	print(result)


T = int(input())
for t in range(0, T):
	A = list(map(int, input().strip().split()))
	n = A[0]
	k = A[1]
	c = -1
	while n != 0:
		c = c + n % k + 1
		n = n // k
	print(c)


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


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


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	c = 0
	l = []
	while n != 0:
		l.append(n % k + 1)
		n = n // k
		c = c + 1
	print(sum(l) - 1)


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


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


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


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	count = 0
	while 1:
		if n % k == 0:
			n //= k
			count += 1
		else:
			r = n % k
			count += r
			n -= r
		if n == 0:
			break
	print(count)
	t -= 1


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

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		print(solve(n, k))
main()


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


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


def solve():
	(a, k) = map(int, input().split())
	c = 0
	while a != 0:
		if a % k == 0:
			a = a // k
			c += 1
		else:
			x = a // k * k
			c += a - x
			a = x
	print(c)
for _ in range(int(input())):
	solve()


i = int(input())
for j in range(i):
	(num, k) = map(int, input().split(' '))
	ct = 0
	while num:
		if num % k:
			ct += num - num // k * k
			num = num // k * k
		else:
			ct += 1
			num //= k
	print(ct)


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


t = int(input())

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


t = int(input())
answer = list()
for i in range(t):
	sum = input()
	a = sum.split(' ')
	(n, k) = (int(a[0]), int(a[1]))
	count = 0
	while n != 0:
		count += n % k + 1
		n = n // k
	answer.append(count - 1)
for ans in answer:
	print(ans)


queries = int(input())
for i in range(queries):
	temp = list(map(int, input().split(' ')))
	counter = 0
	n = temp[0]
	k = temp[1]
	while n != 0:
		if n % k == 0:
			n = n // k
			counter += 1
		elif n // k == 0:
			counter += n % k
			n = n // k
		else:
			counter += n % k + 1
			n = n // k
	print(counter)


n = int(input())
k = 0

def moves(l, k):
	while l[0] > 0:
		k += l[0] % l[1]
		l[0] = l[0] // l[1]
		if l[0] >= 1:
			k += 1
	return k
for i in range(n):
	print(moves(list(map(int, input().split(' '))), k))


def step(n, k):
	if n == 0:
		return 0
	m = n % k
	n -= m
	if m == 0:
		n = n // k
		m = 1
	return m + step(n, k)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(step(n, k))


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


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


def funcion(n, ans):
	while n != 0:
		ans += n % k + 1
		n = n // k
	return ans
aux1 = int(input())
for i in range(aux1):
	aux = input().split(' ')
	(n, k) = (int(aux[0]), int(aux[1]))
	ans = 0
	ans = funcion(n, 0)
	print(ans - 1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if k == 1:
		print(n)
		continue
	nn = n
	tot = 0
	while nn >= k:
		tot += nn % k
		tot += 1
		nn = nn // k
	tot += nn
	print(tot)


import math
t = int(input())
lst = []
for i in range(t):
	d = input()
	d = d.split(' ')
	d = [int(x) for x in d]
	lst.append(d)
for i in lst:
	s = 0
	n = i[0]
	k = i[1]
	if k == 1:
		s = n
	else:
		while n > 0:
			s += n % k + 1
			n = n // k
	print(s - 1)


def solve():
	results = []
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		ans = 0
		while n > 0:
			if n % k == 0:
				ans += 1
				n //= k
			else:
				ans += n - n // k * k
				n -= n - n // k * k
		results.append(ans)
	print('\n'.join(map(str, results)))
solve()


queryCount = int(input())

def HeroToZero(counter, pair):
	if pair[1] > pair[0]:
		print(counter + pair[0])
		return
	elif pair[0] % pair[1] == 0:
		counter += 1
		return HeroToZero(counter, [pair[0] // pair[1], pair[1]])
	else:
		counter += pair[0] % pair[1]
		return HeroToZero(counter, [pair[0] - pair[0] % pair[1], pair[1]])
for query in range(queryCount):
	Q = [int(x) for x in input().split()]
	count = 0
	HeroToZero(count, Q)


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


def fun():
	t = int(input())
	while t > 0:
		(n, k) = map(int, input().split())
		count = 0
		while n != 0:
			if n % k == 0:
				n = n // k
				count += 1
			else:
				ans = n % k
				count = count + ans
				n = n - ans
		print(count)
		t = t - 1
fun()


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	c = 0
	m = n
	while m > 0:
		c += m % k
		m = m // k
		c += 1
	print(c - 1)
	t -= 1


t = int(input().strip())
for i in range(t):
	_ = input().strip().split(' ')
	(n, k) = (int(_[0]), int(_[1]))
	res = 0
	while n != 0:
		res += n % k + 1
		n = n // k
	print(res - 1)


def solve_case(n, k):
	m = n % k
	res = 0
	while n or m:
		if m > 0:
			res += m
			n = n - m
			m = 0
		else:
			res += 1
			n = n // k
			m = n % k
	return res

def solve():
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split())
		result = solve_case(n, k)
		print(result)
solve()


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


t = int(input())
ans = []
for _ in range(t):
	(m, n) = map(int, input().split())
	subans = 0
	while m:
		subans += m % n + 1
		m = m // n
	ans.append(subans - 1)
for a in ans:
	print(a)


import sys
input = sys.stdin.readline

class Problem:

	def __init__(self):
		pass

	def solve(self):
		self._solve()

	def _solve(self):
		for _ in range(int(input())):
			(n, k) = [int(item) for item in 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():
	problem = Problem()
	problem.solve()
main()


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


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


t = int(input())
num = 0
for i in range(t):
	a = input().split(' ')
	n = int(a[0])
	k = int(a[1])
	while n > 0:
		if n % k == 0:
			n = n // k
			num += 1
		else:
			num += n % k
			n -= n % k
	print(num)
	num = 0


def f():
	(n, k) = map(int, input().split())
	a = -1
	while n:
		a += n % k + 1
		n //= k
	return a
for k in range(int(input())):
	print(f())


def hero_to_zero(n, k):
	count = 0
	while n:
		nex = n // k * k
		count = count + (n - nex)
		n = n - (n - nex)
		while n and n % k == 0:
			n = n // k
			count += 1
	return count
t = int(input())
while t:
	nk = list(map(int, input().rstrip().split()))
	n = nk[0]
	k = nk[1]
	print(hero_to_zero(n, k))
	t = t - 1


from math import *
from itertools import *
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	moves = 0
	while n > 0:
		moves += n % k
		n -= n % k
		if n % k == 0 and n != 0:
			n //= k
			moves += 1
	print(moves)


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


t = int(input())
for _ in range(t):
	steps = 0
	(n, k) = [int(i) for i in input().split()]
	while n != 0:
		if n % k == 0:
			n = n // k
			mod = 1
		else:
			mod = n % k
			n = n - mod
		steps = steps + mod
	print(steps)


def main():
	test = int(input())
	for __ in range(test):
		(n, d) = map(int, input().split())
		ans = 0
		while n > 0:
			if n % d == 0:
				n //= d
				ans += 1
			else:
				ans += n % d
				n -= n % d
		print(ans)
main()


T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	cnt = 0
	while N != 0:
		if N - 1 == 0:
			N -= 1
		elif N % K == 0:
			N //= K
		else:
			tmp = N % K
			N -= tmp
			cnt += tmp
			continue
		cnt += 1
	print(cnt)


t = int(input().strip())
for i in range(t):
	_ = input().strip().split(' ')
	(n, k) = (int(_[0]), int(_[1]))
	ans = 0
	while n != 0:
		ans += n % k
		n = n // k
		if n != 0:
			ans += 1
	print(ans)


import math

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


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


for c in range(int(input())):
	(n, k) = map(int, input().split())
	div = 0
	minus = 0
	while n >= k:
		minus += n % k
		div += 1
		n = n // k
	print(div + minus + n)


from decimal import Decimal
n = int(input())
datalist = []
ans = []
for _ in range(n):
	temp = input().split()
	datalist.append([int(temp[0]), int(temp[1])])
for item in datalist:
	n = item[0]
	k = item[1]
	ans.append(0)
	while n != 0:
		ans[-1] += n % k + 1
		n = int(Decimal(n) / Decimal(k))
for each in ans:
	print(each - 1)


val = int(input())
for i in range(1, val + 1, +1):
	count = 0
	(l, r) = input().split(' ')
	(l, r) = (int(l), int(r))
	while l > 0:
		if l % r == 0:
			l = l // r
			count = count + 1
		else:
			count = count + l % r
			l = l - l % r
	print(count)


t = int(input())
while t > 0:
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	count = 0
	if k == 1:
		print(n)
	else:
		while n > 0:
			if n % k == 0:
				count += 1
				n //= k
			else:
				count += n - k * (n // k)
				n -= n - k * (n // k)
		print(count)
	t -= 1


x = int(input())
result = ''
res = 0
for i in range(x):
	res = 0
	word = input()
	(n, k) = word.split()
	n = int(n)
	k = int(k)
	while n != 0:
		delta = int(n % k)
		if delta == 0:
			n = int(n // k)
			res += 1
		else:
			n -= delta
			res += delta
	print(int(res))


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	ans = 0
	while n > 0:
		c = n % k
		if n >= k:
			ans += c + 1
			n //= k
		else:
			ans += c
			break
	print(ans)


t = int(input())
for i in range(t):
	(a, b) = input().strip().split(' ')
	(a, b) = [int(a), int(b)]
	c = 0
	while a > 0:
		if a % b == 0:
			a = a // b
			c = c + 1
		else:
			x = a % b
			c += x
			a -= a % b
	print(c)


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


t = int(input())
while t:
	(n, k) = map(int, input().split())
	cou = 0
	while n != 0:
		cou += n % k
		n -= n % k
		if n == 0:
			break
		cou += 1
		n = n // k
	t -= 1
	print(cou)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7

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

def I():
	return int(input())

def LS():
	return input().split()

def S():
	return input()

def main():
	n = I()
	l = []
	for _ in range(n):
		(a, b) = LI()
		c = 0
		while True:
			if a <= 0:
				break
			x = a % b
			if x == 0:
				a //= b
				c += 1
			else:
				a -= x
				c += x
		l.append(c)
	for x in l:
		print(x)
main()


def func(n, k):
	if n == 0:
		return 0
	elif n % k:
		return n % k + func(n // k * k, k)
	else:
		return 1 + func(n // k, k)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	rls = func(n, k)
	print(rls)


n = int(input())
nk = [list(map(int, input().split())) for i in range(n)]
ans = []
for (n, k) in nk:
	res = 0
	if k == 1:
		ans.append(n)
		continue
	while n:
		if n % k == 0 and k != 1:
			n //= k
			res += 1
		else:
			res += n % k
			n -= n % k
	ans.append(res)
for a in ans:
	print(a)


import sys

def fastio():
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

def debug(*var, sep=' ', end='\n'):
	print(*var, file=sys.stderr, end=end, sep=sep)
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
(t,) = I()
while t:
	t -= 1
	(n, k) = I()
	ans = 0
	while n != 0:
		if n % k == 0:
			n //= k
			ans += 1
		else:
			m = n % k
			ans += m
			n -= m
	print(ans)


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


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


def min(n, k):
	import math
	d = 0
	while n > 0:
		if n % k == 0 and k != 1:
			s = math.log(n, k)
			if s == int(s) and 10 ** s == n:
				d = d + int(s)
				return d + 1
			else:
				d += 1
				n = n // k
		elif k == 1:
			return n
		elif n % k != 0:
			d += int(n % k)
			n = n - int(n % k)
	return d
n = int(input(''))
for i in range(n):
	(a, b) = input('').split()
	d = min(int(a), int(b))
	print(d)


import sys
import math
import bisect

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


t = int(input())
tc = 0
while tc < t:
	(n, k) = map(int, input().split())
	count = 0
	while n != 0:
		md = n % k
		if md == 0:
			n = n // k
			count += 1
		else:
			n -= md
			count += md
	print(int(count))
	tc += 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = 0
	if k <= n:
		while True:
			q = n // k
			r = n - k * q
			if n % k == 0:
				n //= k
				c += 1
			else:
				n -= r
				c += r
			if n == 0:
				break
	else:
		c = n
	print(c)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s = 0
	while a != 0:
		if a % b != 0:
			s += a % b
			a -= a % b
		s += 1
		a = a // b
	print(s - 1)


t = int(input())
inputs = []
for i in range(t):
	ints = input()
	inputs.append(ints.split())
for item in inputs:
	(n, k) = (int(item[0]), int(item[1]))
	i = 0
	while n != 0:
		if n % k == 0:
			n = n // k
			i += 1
		else:
			i += n % k
			n = int(n // k * k)
	print(int(i))


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


import math
t = int(input())
for x in range(t):
	(n, k) = map(int, input().split())
	steps = 0
	while n > 0:
		if k ** math.floor(math.log(n, k)) == n:
			steps += math.floor(math.log(n, k)) + 1
			break
		elif n % k == 0:
			n //= k
			steps += 1
		else:
			steps += n % k
			n -= n % k
	print(int(steps))


query = int(input())
while query > 0:
	(n, k) = map(int, input().split())
	times = 0
	while n > 0:
		if n % k == 0:
			times = times + 1
			n = n // k
		else:
			times += n % k
			n = n - n % k
	print(times)
	query -= 1


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


def sv():
	(N, K) = map(int, input().split())
	ans = 0
	while N:
		if N % K:
			d = N // K * K
			ans += N - d
			N = d
		if not N:
			break
		N //= K
		ans += 1
	print(ans)
TC = int(input())
for tc in range(TC):
	sv()


for i in range(int(input())):
	data = tuple(map(int, input().split(' ')))
	n = data[0]
	k = data[1]
	c = 0
	if k > n:
		print(n)
		continue
	while n != 0:
		rem = n % k
		if rem == 0:
			c += 1
		else:
			c += rem + 1
		n = n // k
	print(c - 1)


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


def main():
	buf = input()
	t = int(buf)
	nk = []
	for i in range(t):
		buf = input()
		buflist = buf.split()
		nk.append((int(buflist[0]), int(buflist[1])))
	for x in nk:
		n = x[0]
		k = x[1]
		c = 0
		while n > 0:
			rem = n % k
			if rem == 0:
				n //= k
				c += 1
			else:
				n -= rem
				c += rem
		print(c)
main()


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


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


for q in range(int(input())):
	(n, k) = list(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)


t = int(input())
a = []
for i in range(t):
	q = 0
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	while n > 0:
		q += n % k
		n = n // k
		if n > 0:
			q += 1
	a.append(q)
for i in range(t):
	print(a[i])


import sys
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *
readl = lambda : list(map(int, sys.stdin.readline().split()))
readt = lambda : tuple(map(int, sys.stdin.readline().split()))
read = lambda : sys.stdin.readline().rstrip()
readi = lambda : int(read())
readmi = lambda : map(int, sys.stdin.readline().split())
readms = lambda : map(str, sys.stdin.readline().split())
n = readi()
for i in range(n):
	(m, k) = readmi()
	count = 0
	while m > 0:
		if m % k == 0:
			count += 1
			m //= k
		else:
			t = m % k
			count += t
			m -= t
	print(count)


from sys import stdin
t = int(stdin.readline().rstrip())
while t > 0:
	l = list(map(int, stdin.readline().split()))
	(n, k) = (l[0], l[1])
	c = 0
	while n != 0:
		if n % k == 0:
			c += 1
			n = n // k
		else:
			c += n % k
			n -= n % k
	print(c)
	t -= 1


import sys

def main():
	_ = int(sys.stdin.readline().rstrip())
	lines = sys.stdin.read().split('\n')
	for line in lines:
		if len(line) < 3:
			continue
		(n, k) = [int(x) for x in line.split(' ')]
		i = 0
		while n > 0:
			if n % k == 0:
				i += 1
				n = n // k
			else:
				m = n % k
				n -= m
				i += m
		print(i)
main()


def r(a, x):
	(a, b) = divmod(a, x)
	count = 0
	while a >= x:
		count += b + 1
		(a, b) = divmod(a, x)
	return (count, a, b)
tc = int(input())
for _ in range(tc):
	(a, x) = map(int, input().split())
	(c, d, e) = r(a, x)
	print(c + d + e + (0 if c == 0 and d == 0 else 1))


import sys
sys.setrecursionlimit(1048576)
RI = lambda : [int(x) for x in input().strip().split()]
from collections import defaultdict as df
import heapq
import random
infinite = float('inf')
t = int(input())
for i in range(t):
	(n, k) = RI()
	count = 0
	while n > 0:
		temp = n % k
		count += temp
		n -= temp
		n = n // k
		if n != 0:
			count += 1
	print(int(count))


import math
t = int(input())
for i in range(0, t):
	vars = list(map(int, input().rstrip().split()))
	(n, k, steps) = (vars[0], vars[1], 0)
	while n != 0:
		temp = n % k
		if temp == 0:
			n = n // k
			steps += 1
		else:
			n -= temp
			steps += temp
	print(int(steps))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans = 0
	while a > 0:
		temp = a % b
		ans += temp
		a -= temp
		if a > 0:
			a //= b
			ans += 1
	print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = 0
	while n > k - 1:
		c += n % k
		c += 1
		n //= k
	c += n
	print(c)


def resuelve(n, k):
	cont = 0
	while n != 0:
		if n % k == n:
			cont += n
			return cont
		nn = n // k
		x = nn * k
		cont += 1
		cont += n - x
		n = nn
	return cont
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	print(resuelve(n, k))


def xdd(n: int, k: int):
	i = 0
	while n != 0:
		i += n % k
		i += 1
		n = n // k
	return i - 1
c = int(input())
A = []
i = 0
for xd in range(c):
	(a, b) = input().split()
	A.append([int(a), int(b)])
q = 0
for xd in range(c):
	h = A[q][0]
	j = A[q][1]
	print(xdd(h, j))
	q += 1


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


N = int(input())
for i in range(N):
	Count = 0
	X = list(map(int, input().split()))
	while X[0] != 0:
		if X[0] % X[1] == 0:
			X[0] = X[0] // X[1]
			Count += 1
		else:
			Count += X[0] % X[1]
			X[0] -= X[0] % X[1]
	print(Count)


t = int(input())
for q in range(0, t):
	(n, k) = input().split()
	(n, k) = [int(n), int(k)]
	count = 0
	while n > 0:
		if n % k == 0:
			n = n // k
			count += 1
		else:
			count += n % k
			n = n - n % k
	print(count)


test = int(input())
while test > 0:
	s = input()
	n = s.split()
	a = int(n[0])
	b = int(n[1])
	ans = 0
	while a > 0:
		if a % b == 0:
			a = a // b
			ans += 1
		else:
			mod = a % b
			ans += mod
			a -= mod
	print(ans)
	test -= 1


for i in range(int(input())):
	a = [int(i) for i in input().split()]
	count = 0
	while a[0] != 0:
		if a[0] % a[1] == 0:
			a[0] = a[0] // a[1]
			count += 1
		else:
			rem = a[0] % a[1]
			a[0] -= rem
			count += rem
	print(count)


n = int(input())
for _ in range(n):
	(a, b) = map(int, input().split())
	i = 0
	while True:
		if a % b == 0:
			a = a // b
			i += 1
		else:
			x = a % b
			i += x
			a = a - x
		if a <= 0:
			break
	print(i)


def fun(x, n, steps):
	if x == 0:
		return steps
	else:
		u = x % n
		if u == 0:
			x = x // n
			steps += 1
		else:
			x -= u
			steps += u
		return fun(x, n, steps)
x = int(input())
for i in range(x):
	arr = list(map(int, input().split()))
	print(fun(arr[0], arr[1], 0))


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	ct = 0
	while n:
		ct = ct + n % k
		if n >= k:
			ct = ct + 1
		n = n // k
	print(ct)


def Input(T, n, k):
	T = int(input())
	for i in range(T):
		(tmpn, tmpk) = list(map(int, input().split()))
		n.append(tmpn)
		k.append(tmpk)
	return (T, n, k)

def Processing(T, n, k):
	for i in range(T):
		result = int(0)
		x = int(n[i])
		y = int(k[i])
		while x != 0:
			if x < y:
				result += x
				break
			if x % y == 0:
				result += 1
				x = x // y
				continue
			tmp = int(x // y * y)
			result += int(x - tmp + 1)
			x = int(tmp)
			x = x // y
		print(int(result), end='\n')
n = []
k = []
T = 0
(T, n, k) = Input(T, n, k)
Processing(T, n, k)


def soln(n, k):
	count = 0
	if k == 1:
		return n
	while n > 0:
		if n < k:
			count += n
			n = 0
			continue
		elif n == k:
			n = 0
			count += 2
			continue
		elif n % k == 0:
			n = n // k
			count += 1
		else:
			count += n % k
			n = n - n % k
	return count
t = int(input())
for z in range(t):
	(n, k) = list(map(int, input().split()))
	ans = soln(n, k)
	print(ans)


N = int(input())

def keisan(n, k):
	if k == 1:
		return n
	ret = 0
	while n > 0:
		if n % k != 0:
			ret += n % k
			n -= n % k
		else:
			ret += 1
			n //= k
	return ret
for k in range(N):
	(a, b) = map(int, input().split())
	print(keisan(a, b))


import math

def input_ints():
	return map(int, input().split())
t = int(input())
for _ in range(t):
	(n, k) = input_ints()
	i = 0
	while n > 0:
		p = n % k
		i += p
		n -= p
		while n > 0 and n % k == 0:
			n //= k
			i += 1
	print(i)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	sum = 0
	while x != 0:
		if x % y == 0:
			x = x // y
			sum += 1
		else:
			sum += x % y
			x -= x % y
	print(sum)


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


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	cnt = 0
	while n:
		if not n % k:
			n //= k
			cnt += 1
		elif n < k:
			cnt += n
			break
		else:
			cnt += n % k
			n -= n % k
	print(cnt)


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


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


t = int(input())

def answer(n, k):
	step = 0
	while n not in [0, 1]:
		q = n % k
		n = n - q
		step += q
		if n != 0:
			n = n // k
			step += 1
	if n == 1:
		step += 1
	print(step)
for i in range(t):
	(n, k) = map(int, input().split(' '))
	answer(n, k)


t = int(input())

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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = 0
	while n:
		(n, m) = divmod(n, k)
		x += m + 1
	print(x - 1)


def main():
	t = int(input())
	for case in range(t):
		(n, k) = map(int, input().split())
		cnt = 0
		while True:
			if n == 0:
				break
			rem = n % k
			if rem == 0:
				n = n // k
				cnt = cnt + 1
			else:
				n = n - rem
				cnt = cnt + rem
		print(cnt)
main()


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


for x in range(int(input())):
	count = 0
	(x, k) = map(int, input().strip().split()[:4])
	while x > 0:
		r = x % k
		if r == 0:
			x = x // k
			count += 1
		else:
			x -= r
			count += r
	print(count)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ans = 0
	while n != 0:
		if n < k:
			ans += n
			break
		c = n // k
		delta = n - c * k
		ans += delta + 1
		n = c
	print(ans)


T = int(input())
test = 0
while test < T:
	res = 0
	NK = input()
	(N, K) = NK.split(' ')
	N = int(N)
	K = int(K)
	while N > 0:
		res += N % K + 1
		N = N // K
	print(res - 1)
	test += 1


t = int(input())
for _ in range(t):
	(a, b) = [int(x) for x in input().strip().split()]
	rem = 0
	count = 0
	while a >= b:
		rem += a % b
		a = a // b
		count += 1
	count += a
	res = count + rem
	print(res)


import atexit
import io
import sys
_I_B = sys.stdin.read().splitlines()
input = iter(_I_B).__next__
_O_B = io.StringIO()
sys.stdout = _O_B

@atexit.register
def write():
	sys.__stdout__.write(_O_B.getvalue())

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		steps = 0
		while n:
			cur = n % k
			steps += cur
			n -= cur
			if n:
				n //= k
				steps += 1
		print(steps)
main()


def main():
	for i in range(int(input())):
		(n, k) = map(int, input().split())
		step = 0
		while n > 0:
			if n % k == 0:
				step += 1
				n //= k
			else:
				aux = n // k
				aux *= k
				step += n - aux
				n = aux
		print(step)
main()


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


import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

def solve():
	(N, K) = map(int, input().split())
	ans = 0
	while N:
		r = N % K
		ans += r
		N -= r
		if N == 0:
			break
		N //= K
		ans += 1
	print(ans)
n = int(input())
for _ in range(n):
	solve()


def rek(n):
	if n // k == 0:
		return n
	return n - n // k * k + 1 + rek(n // k)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	print(rek(n))


import math
for test in range(int(input().strip())):
	(n, k) = [int(i) for i in input().strip().split(' ')]
	count = 0
	while n > 0:
		if n % k ** 5 == 0:
			n //= k ** 5
			count += 5
		elif n % k == 0:
			n //= k
			count += 1
		else:
			count += n % k
			n -= n % k
	print(count)


def cal(n, k):
	if n == k:
		return 2
	if n < k:
		return n
	step = 0
	while n != 0:
		if n < k:
			step += n
			break
		if n % k == 0:
			n //= k
			step += 1
		else:
			y = n // k
			q = y * k
			step += n - q
			n -= n - q
	return step
for i in range(int(input())):
	(n, k) = map(int, input().split())
	print(cal(n, k))


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


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


queries = int(input())
for i in range(queries):
	(n, k) = [*map(int, input().split())]
	count = 0
	while n > 0:
		if n % k == 0:
			new = n // k
			count += 1
			n = new
		else:
			resto = n % k
			count += resto
			n -= resto
	print(count)


import sys
t = -1
for line in sys.stdin:
	if t == -1:
		t = int(line)
		continue
	if t == 0:
		break
	line = list(line.split())
	n = int(line[0])
	k = int(line[1])
	operations_count = 0
	while n != 0:
		remainder = n % k
		if remainder == 0:
			n //= k
			operations_count += 1
		else:
			n -= remainder
			operations_count += remainder
	print(operations_count)
	t -= 1


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


def zero(n, k):
	count = 0
	while n > 0:
		y = n // k
		count += n - y * k + 1
		n = min(y, n - 1)
	if k != 1:
		count -= 1
	return count
t = int(input())
lst = list()
for i in range(t):
	(x, y) = [int(j) for j in input().split()]
	lst.append(zero(x, y))
for elem in lst:
	print(elem)


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


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


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


import itertools

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

def output_list(v):
	print(' '.join((str(x) for x in v)))

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = input_ints()
		ans = 0
		while n:
			if n % k:
				ans += n % k
				n = n // k * k
			else:
				ans += 1
				n //= k
		print(ans)
main()


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


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


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


import math as mt
import sys, string
from collections import Counter, defaultdict
input = sys.stdin.readline
I = lambda : int(input())
M = lambda : map(int, input().split())
ARR = lambda : list(map(int, input().split()))

def printARR(arr):
	for e in arr:
		print(e, end=' ')
	print()

def main():
	(n, k) = M()
	if k == 1:
		print(n)
	ans = 0
	while n:
		if n % k == 0:
			n = n // k
			ans += 1
		else:
			tmp = n % k
			n -= tmp
			ans += tmp
	print(ans)
tc = 1
tc = I()
for _ in range(tc):
	main()


t = int(input().strip())
for i in range(t):
	array = input().strip().split(' ')
	(a, k) = (int(array[0]), int(array[1]))
	respuesta = 0
	while a != 0:
		respuesta += a % k + 1
		a = a // k
	print(respuesta - 1)


def count(n, k):
	Count = 0
	while n > 0:
		Count += n % k
		n //= k
		if n > 0:
			Count += 1
	print(Count)
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	count(n, k)


for _ in range(int(input())):
	s = input().split()
	(n, k) = (int(s[0]), int(s[1]))
	cnt = 0
	while n >= k:
		nk = n % k
		if nk > 0:
			n -= nk
			cnt += nk
		else:
			n //= k
			cnt += 1
	print(cnt + n)


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


import sys
import math
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
mod = 1000000007

def nospace(l):
	ans = ''.join((str(i) for i in l))
	return ans
t = int(input())
for tt in range(t):
	(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)
if fileoperation:
	sys.stdout = orig_stdout
	sys.stdin = orig_stdin
	inputfile.close()
	outputfile.close()


q = int(input())
while q:
	q = q - 1
	(num, div) = list(map(int, input().split()))
	x = 0
	while num:
		t = num - num // div * div
		x = x + (num - num // div * div)
		num = num // div
		if num != 0:
			x = x + 1
	print(x)


t = 0
n = []
k = []
a = 0

def Input():
	global n, k, t
	t = int(input())
	for index in range(t):
		(x, y) = list(map(int, input().split()))
		n.append(x)
		k.append(y)

def Output():
	global n, k, t
	for index in range(t):
		count = 0
		while n[index] != 0:
			if n[index] % k[index] == 0:
				count += 1
				n[index] = n[index] // k[index]
			else:
				a = int(n[index] % k[index])
				count = count + a
				n[index] = n[index] - a
		print(count)
Input()
Output()


import math
tcase = int(input())
while tcase > 0:
	tcase -= 1
	arr = input().split()
	n = int(arr[0])
	k = int(arr[1])
	steps = 0
	if k > n:
		print(n)
	elif k == n:
		print('2')
	else:
		while n != 0:
			if n % k == 0:
				n = n // k
			elif k > n:
				steps += n
				break
			elif n > k:
				steps += n % k
				n -= n % k
				continue
			elif n == k:
				steps += 2
				break
			else:
				n -= 1
			steps += 1
		print(steps)


for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	ans = 0
	while n > 0:
		if n % k == 0:
			n = n // k
			ans += 1
		else:
			near = n // k * k
			ans += n - near
			n -= n - near
		if n <= 0:
			break
	print(ans)


x = int(input())
a = 0
for i in range(x):
	a = 0
	(y, z) = [int(i) for i in input().split()]
	while y != 0:
		if y % z == 0:
			y //= z
			a += 1
		else:
			a += y % z
			y -= y % z
	print(a)


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


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


t = int(input())
for I in range(t):
	(n, k) = [int(i) for i in input().split()]
	ans = 0
	while n:
		while n % k == 0:
			n //= k
			ans += 1
		if n < k:
			ans += n
			break
		mul = n // k * k
		ans += n - mul
		n = mul
	print(ans)


n = int(input())
while n:
	(n1, k) = map(int, input().split())
	ans = 0
	while n1 != 0:
		ans += n1 % k
		n1 = n1 // k
		if n1 != 0:
			ans += 1
	print(ans)
	n -= 1


c = int(input())
for i in range(c):
	(n, m) = map(int, input().split())
	s = 0
	while n > -1:
		r = n % m
		if n >= m:
			s += r + 1
			n = int(n // m)
		if n < m:
			r = n % m
			s += r
			break
	print(s)


def main():
	l = int(input())
	for i in range(l):
		(v, k) = [int(v) for v in input().split()]
		s = 0
		while v != 0:
			s += v % k
			v = v // k
			s += 1
		print(s - 1)
main()


t = int(input())
s = []
for hhjh in range(0, t):
	(n, k) = map(int, input().split())
	g = 0
	while n != 0:
		if n % k == 0:
			n = n // k
			g += 1
		else:
			m = n // k
			g = g + (n - m * k)
			n = m * k
	s.append(g)
for i in s:
	print(i)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = 0
	while n:
		if n % k == 0:
			n = n // k
			c += 1
		else:
			r = n % k
			c += r
			n -= r
	print(c)


t = int(input())
for i in range(t):
	n = [int(i) for i in input().split()]
	count = 0
	while n[0] > 0:
		while n[0] % n[1] == 0:
			n[0] = n[0] // n[1]
			count += 1
		c = n[0] % n[1]
		n[0] -= c
		count += c
	print(count)


for ___ in range(int(input())):
	(_, __) = map(int, input().split())
	x = 0
	while _ > 0:
		if _ % __ == 0:
			x += 1
		else:
			x += _ % __ + 1
		_ //= __
	print(x - 1)


import math

def check(k, n):
	p = math.log(k) / math.log(n)
	p = p // 1
	if n ** p == k:
		return p
	else:
		return 0

def num(k, n):
	count = 0
	while k > 0:
		if k < n:
			count += k
			break
		elif check(k, n) > 0:
			count += int(check(k, n) + 1)
			break
		elif k % n == 0:
			k = k // n
			count += 1
		else:
			p = k // n
			l = k - p * n
			k = k - l
			count += l
	print(count)
T = int(input())
for i in range(T):
	(k, n) = map(int, input().split())
	num(k, n)


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


n = int(input())
for i in range(n):
	x = [int(i) for i in input().split()]
	a = x[0]
	b = x[1]
	d = 0
	k = 0
	c3 = 0
	while a != 0:
		c = a // b
		c2 = c * b
		if c2 != a:
			c3 = a - c2
			k = k + c3
			a = a - c3
		else:
			a = c
			k = k + 1
	print(k)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	(N, K) = getInts()
	ans = 0
	while N:
		if N % K > 0:
			ans += N % K
			N -= N % K
		else:
			ans += 1
			N //= K
	return ans
for _ in range(getInt()):
	print(solve())


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
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

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)


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


def ii():
	return int(input())

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

def li():
	return list(mi())
t = ii()
for _ in range(t):
	(n, k) = mi()
	c = 0
	while n != 0:
		c += n % k
		n -= n % k
		c += 1
		n //= k
	print(c - 1)


t = int(input())

def steps(n, k):
	step = 0
	while n:
		if n % k == 0:
			n = n // k
			step += 1
		else:
			step += n - n // k * k
			n = n // k * k
	return step
a = [[int(j) for j in input().split(' ')] for i in range(1, t + 1)]
for i in range(1, t + 1):
	print(steps(a[i - 1][0], a[i - 1][1]))


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


from sys import stdin
r = stdin.readline
t = int(r().strip())
for e in range(t):
	(n, k) = map(int, r().split())
	total = 0
	while n > 0:
		res = n % k
		if res == 0:
			n = n // k
			total += 1
		else:
			total += res
			n -= res
	print(int(total))


Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]
for (N, K) in Query:
	step = 0
	while N > 0:
		if N % K == 0:
			N //= K
			step += 1
		else:
			a = N % K
			N -= a
			step += a
	print(step)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	steps = -1
	while n >= 1:
		n1 = n // k
		steps += 1
		steps += n - n1 * k
		n = n1
	print(steps)


from math import log
for _ in range(int(input().strip())):
	(n, k) = map(int, input().strip().split())
	s = 0
	while n > 0:
		if n % k == 0:
			n //= k
			s += 1
		else:
			s += n % k
			n = n - n % k
	print(s)


import sys
from collections import Counter

def input():
	return sys.stdin.readline().strip()

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def main():
	(a, s) = rinput()
	t = 0
	while a != 0:
		if a < s:
			t += a
			a = 0
		else:
			t += a % s
			a -= a % s
			while a % s == 0:
				t += 1
				a //= s
	print(t)
for i in range(int(input())):
	main()


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


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


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


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


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()


for _ in [0] * int(input()):
	(n, k) = map(int, input().split())
	r = 0
	while n:
		r += n % k + 1
		n = n // k
	print(r - 1)


t = int(input())
c = 0
while t > 0:
	(n, k) = map(int, input().split())
	while n > 0:
		if n % k == 0:
			n = n // k
			c = c + 1
		else:
			x = n % k
			n = n - x
			c = c + x
	print(c)
	c = 0
	t = t - 1


for _ in [0] * int(input()):
	(n, k) = [int(x) for x in input().split()]
	steps = 0
	while n > 0:
		temp = n % k
		steps += temp
		n -= temp
		if n > 0:
			steps += 1
			n //= k
	print(steps)


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


from sys import stdin, stdout
import math, sys
from itertools import permutations, combinations
from collections import defaultdict, deque, OrderedDict
import bisect as bi
import heapq

def I():
	return int(input())

def In():
	return map(int, input().split())

def main():
	try:
		(a, b) = In()
		ans = 0
		while a > 0:
			temp = a % b
			if temp == 0:
				ans += 1
				a = a // b
			else:
				ans += temp
				a -= temp
		print(ans)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(I()):
	main()


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


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


import math
n = int(input())
while n > 0:
	n -= 1
	[m, k] = list(map(int, input().split()))
	c = 0
	while m >= k:
		if m % k == 0:
			c += 1
		else:
			c += m % k + 1
		m = m // k
	c += m
	print(c)


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


ll = lambda : list(map(int, input().split()))
nn = lambda : int(input())
testcases = 1
testcases = nn()
for testcase in range(testcases):
	[n, k] = ll()
	steps = 0
	while n != 0:
		if n % k == 0:
			n = n // k
			steps += 1
		else:
			ps = n % k
			n -= ps
			steps += ps
	print(steps)


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


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	cont = 0
	while a != 0:
		if a % b == 0:
			a //= b
			cont += 1
		else:
			cont += a % b
			a = a - a % b
	print(round(cont))


n = int(input())
for i in range(n):
	x = 0
	(c, d) = [int(x) for x in input().split()]
	while c != 0:
		if c % d == 0:
			c = c // d
			x = x + 1
		elif c > d:
			x = x + (c - c // d * d)
			c = c - (c - c // d * d)
		else:
			x = x + c
			c = 0
	print(x)


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


tt = int(input())
while tt:
	(n, k) = map(int, input().split())
	cnt = 0
	while n != 0:
		if n % k == 0:
			n = n // k
			cnt += 1
		else:
			re = n % k
			n = n - re
			cnt += re
	print(int(cnt))
	tt -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	cnt = 0
	while n:
		(q, r) = divmod(n, k)
		if r == 0:
			cnt += 1
			n = q
		else:
			if q:
				cnt += r + 1
			else:
				cnt += r
			n = q
	print(cnt)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def main():
	n = I()
	aa = [LI() for _ in range(n)]
	r = []
	for (a, b) in aa:
		t = 0
		while a >= b:
			k = a % b
			t += k
			a -= k
			if a >= b:
				t += 1
				a //= b
		r.append(t + a)
	return JA(r, '\n')
print(main())


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	count = 0
	(a, b) = (int(n // k), int(n % k))
	while n > 0:
		if k > n:
			(a, b) = (0, int(n % k))
		else:
			(a, b) = (math.floor(n // k), int(n % k))
		n = a
		if a == 0:
			count += b
		else:
			count += b + 1
	print(count)


n = int(input())
for i in range(n):
	s1 = list(map(int, input().split()))
	div = s1[0] % s1[1]
	cnt = div
	abc = s1[0] - div
	while abc != 0:
		if abc % s1[1] == 0:
			while abc % s1[1] == 0:
				abc = abc // s1[1]
				cnt += 1
		else:
			cnt += abc % s1[1]
			abc -= abc % s1[1]
	print(cnt)


tests = int(input())
while tests:
	a = [int(t) for t in input().split()]
	res = 0
	while a[0] != 0:
		if a[0] % a[1] == 0:
			res += 1
			a[0] = a[0] // a[1]
		else:
			res += a[0] - a[0] // a[1] * a[1]
			res += 1
			a[0] = a[0] // a[1]
	print(res - 1)
	tests -= 1


def f(n, k):
	if n == 0:
		return -1
	else:
		return n % k + 1 + f(n // k, k)
t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split(' ')]
	print(f(n, k))


def FHtZ(n, k):
	times = 0
	if k == 1:
		times = n
	else:
		while n > 0:
			nk = n % k
			if nk == 0:
				n = n // k
				times += 1
			else:
				times += nk
				n += -1 * nk
	return times

def main():
	results = []
	for _ in range(int(input())):
		inl = input().split()
		l = [int(inl[i]) for i in (0, 1)]
		results.append(FHtZ(l[0], l[1]))
	for i in results:
		print(i)
if '__main__' == __name__:
	main()


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


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)


import math
t = int(input())
for w in range(t):
	(n, k) = (int(i) for i in input().split())
	c = 0
	while n > 0:
		if n % k == 0:
			n //= k
			c += 1
		else:
			n1 = n % k
			n -= n1
			c += n1
	print(c)


t = int(input())
ans = []
for i in range(t):
	(n, k) = map(int, input().split())
	res = 0
	while n > 0:
		if n % k == 0:
			n //= k
			res += 1
		else:
			t = n % k
			n -= t
			res += t
	ans.append(int(res))
print(*ans, sep='\n')


from sys import stdin, stdout
t = int(stdin.readline().strip())
for caso in range(t):
	(n, k) = map(int, stdin.readline().strip().split())
	pasos = 0
	while n > 0:
		if n % k == 0:
			n //= k
			pasos += 1
		else:
			z = n // k * k
			pasos += n - z
			n = z
	stdout.write('%d\n' % pasos)


vstup1 = int(input())
for i in range(vstup1):
	vstup2 = list(map(int, input().split()))
	n = vstup2[0]
	k = vstup2[1]
	counter = 0
	while n:
		if n % k:
			zvysok = n % k
			n -= zvysok
			counter += zvysok
		else:
			n = n // k
			counter += 1
	print(int(counter))


T = int(input())

def solve(N, K):
	steps = 0
	while N >= K:
		if N % K == 0:
			N //= K
			steps += 1
		else:
			prev = N
			N //= K
			steps += prev - N * K + 1
	steps += N
	return steps
for _ in range(T):
	(N, K) = map(int, input().split())
	print(solve(N, K))


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


q = int(input())
while q:
	(x, y) = [int(x) for x in input().split()]
	i = 0
	while x:
		if x % y == 0:
			i = i + 1
			x = x // y
		else:
			i = i + x % y
			x = x - x % y
	print(i)
	q = q - 1


a = int(input())
z = []
for i in range(0, a):
	(b, c) = map(int, input().split())
	k = 0
	while b != 0:
		if b % c == 0:
			b = b // c
			k += 1
		else:
			k += b % c
			b = b - b % c
	z.append(k)
for i in range(0, a):
	print(z[i])


queries = int(input())
for _ in range(queries):
	(n, k) = map(int, input().split())
	count = 0
	while n != 0:
		r = n % k
		n = n // k
		count = count + r + 1
	print(count - 1)


x = int(input())
l = []
for i in range(x):
	(a, b) = tuple(input().split())
	a = int(a)
	b = int(b)
	count = 0
	while a != 0:
		if a % b == 0:
			a = a // b
			count += 1
		else:
			x = a % b
			a = a // b
			count += x + 1
	l.append(count - 1)
for i in l:
	print(i)


from sys import setcheckinterval, stdin
setcheckinterval(1000)
iin = lambda : int(stdin.readline())
lin = lambda : list(map(int, stdin.readline().split()))
for _ in range(iin()):
	(n, k) = lin()
	ch = 0
	while n:
		if n % k:
			ch += n % k
			n -= n % k
		else:
			ch += 1
			n //= k
	print(ch)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ANS = 0
	while n > 0:
		x = n // k * k
		ANS += n - x
		n = x
		if n == 0:
			break
		else:
			n //= k
			ANS += 1
	print(ANS)


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


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


t = int(input())
from math import log

def base(n, k):
	a = []
	for i in range(int(log(n, k) + 2)):
		a.append(n % pow(k, 1))
		n -= n % pow(k, 1)
		n //= pow(k, 1)
	return a
for _ in range(t):
	(n, k) = map(int, input().split())
	a = base(n, k)
	ans = 0
	last = 0
	for i in range(len(a)):
		if a[i]:
			ans += a[i] + (i - last)
			last = i
	print(ans)


c = int(input())
l = []
for j in range(c):
	(n, k) = map(int, input().split())
	temp = 0
	while n:
		div = n % k
		if div == 0:
			n = int(n) // int(k)
			temp += 1
			div = n % k
		if div != 0:
			temp += div
			n -= div
	l.append(int(temp))
for i in range(len(l)):
	print(l[i])


def solve():
	(n, k) = map(int, input().split())
	ans = 0
	while n >= k:
		m = k * (n // k)
		ans += n - m
		n = m
		n //= k
		ans += 1
	print(ans + n)

def main():
	for _ in range(int(input())):
		solve()
	return 0
main()


for w in range(int(input())):
	(n, k) = map(int, input().strip().split())
	c = 0
	while n > 0:
		if n % k == 0:
			n = n // k
			c += 1
		else:
			p = n % k
			n -= p
			c += p
	print(c)


t = int(input())
for e in range(t):
	data = input().split()
	(n, k) = (int(data[0]), int(data[1]))
	count = 0
	while n != 0:
		count += n % k + 1
		n = n // k
	print(count - 1)


from collections import defaultdict, OrderedDict, Counter
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from queue import Queue, PriorityQueue
from heapq import heapify, heappop, heappush
from statistics import median
from math import gcd, sqrt, floor, factorial, ceil, log2, log10
import fractions
import copy
from copy import deepcopy
import sys
import io
sys.setrecursionlimit(10 ** 8)
import math
import os
import bisect
import collections
mod = pow(10, 9) + 7
import random
from random import random, randint, randrange

def ncr(n, r, p=mod):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def normalncr(n, r):
	r = min(r, n - r)
	count = 1
	for i in range(n - r, n + 1):
		count *= i
	for i in range(1, r + 1):
		count //= i
	return count
inf = float('inf')
adj = defaultdict(set)
visited = defaultdict(int)

def addedge(a, b):
	adj[a].add(b)
	adj[b].add(a)

def bfs(v):
	q = Queue()
	q.put(v)
	visited[v] = 1
	while q.qsize() > 0:
		s = q.get_nowait()
		print(s)
		for i in adj[s]:
			if visited[i] == 0:
				q.put(i)
				visited[i] = 1

def dfs(v, visited):
	if visited[v] == 1:
		return
	visited[v] = 1
	print(v)
	for i in adj[v]:
		dfs(i, visited)

def reverse_bisect_right(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if x > a[mid]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def reverse_bisect_left(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if x >= a[mid]:
			hi = mid
		else:
			lo = mid + 1
	return lo

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

def get_str_list_in_int():
	return [int(i) for i in list(input())]

def get_str_list():
	return list(input())

def get_map():
	return map(int, input().split())

def input_int():
	return int(input())

def matrix(a, b):
	return [[0 for i in range(b)] for j in range(a)]

def swap(a, b):
	return (b, a)

def find_gcd(l):
	a = l[0]
	for i in range(len(l)):
		a = gcd(a, l[i])
	return a

def is_prime(n):
	sqrta = int(sqrt(n))
	for i in range(2, sqrta + 1):
		if n % i == 0:
			return 0
	return 1

def prime_factors(n):
	sqrta = int(sqrt(n))
	for i in range(2, sqrta + 1):
		if n % i == 0:
			return [i] + prime_factors(n // i)
	return [n]
nc = 'NO'
yc = 'YES'
ns = 'No'
ys = 'Yes'
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def no(n, k):
	if n == 0:
		return 0
	if n < k:
		return n
	if n % k == 0:
		return 1 + no(n // k, k)
	return n % k + no(n - n % k, k)
t = int(input())
for i in range(t):
	(n, k) = get_map()
	ans = no(n, k)
	print(ans)


import math

def func(n, k):
	(s, e) = (0, int(1e+19))
	while s <= e:
		m = (s + e) // 2
		if k * m > n:
			e = m - 1
		else:
			s = m + 1
	return k * e
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ans = 0
	while n > 0:
		f = func(n, k)
		if f == 0:
			ans += n
		else:
			ans += n - f + 1
		n = f // 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)


def solve_case(n, k):
	if n < k:
		return n
	elif n % k == 0:
		return 1 + solve_case(n // k, k)
	else:
		return n % k + solve_case(n - n % k, k)

def solve():
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split())
		result = solve_case(n, k)
		print(result)
solve()


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


def go_to_zero(n, k):
	res = 0
	if n < k:
		return n
	while n > 0:
		if n % k == 0:
			n = n // k
			res += 1
		else:
			res += n % k
			n -= n % k
	return res
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(go_to_zero(n, k))


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = 0
	while n != 0:
		if n < k:
			s += n
			n -= n
		elif n % k == 0:
			n = n // k
			s += 1
		elif n % k != 0:
			s = s + n % k + 1
			n = n // k
	print(s)
	t -= 1


number_of_queries = 0
arr_n = []
arr_k = []

def Input(number_of_queries, arr_n, arr_k):
	number_of_queries = int(input())
	for index in range(number_of_queries):
		(x, y) = list(map(int, input().split()))
		arr_n.append(x)
		arr_k.append(y)
	return (number_of_queries, arr_n, arr_k)

def Minimum_number_of_steps(divided, divisor):
	count = 0
	while divided != 0:
		count += divided % divisor
		count += 1
		divided = divided // divisor
	count -= 1
	return count

def Output(number_of_queries, arr_n, arr_k):
	for index in range(number_of_queries):
		print(Minimum_number_of_steps(arr_n[index], arr_k[index]))
	return (number_of_queries, arr_n, arr_k)
(number_of_queries, arr_n, arr_k) = Input(number_of_queries, arr_n, arr_k)
(number_of_queries, arr_n, arr_k) = Output(number_of_queries, arr_n, arr_k)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from math import sqrt, floor, factorial, gcd, log
from collections import deque, Counter, defaultdict
from itertools import permutations, combinations
from math import gcd
from bisect import bisect
input = lambda : sys.stdin.readline().rstrip('\r\n')
read = lambda : list(map(int, input().strip().split(' ')))

def solve():
	for _ in range(int(input())):
		(n, k) = read()
		ans = 0
		while n:
			if n % k:
				ans += n % k
				n -= n % k
			else:
				ans += 1
				n //= k
		print(ans)
solve()


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


def f(n, k):
	ans = 0
	while n > 0:
		if n % k == 0:
			n = n // k
			ans += 1
		else:
			ans += n % k
			n -= n % k
	return ans
t = int(input())
for you in range(t):
	l = input().split()
	n = int(l[0])
	k = int(l[1])
	print(f(n, k))


import sys
runs = int(sys.stdin.readline().rstrip())
for x in range(runs):
	line = sys.stdin.readline().rstrip().split(' ')
	one = int(line[0])
	two = int(line[1])
	steps = 0
	while one != 0:
		diff = one // two * two
		steps += one - diff
		one = diff
		one //= two
		steps += 1
	print(steps - 1)


from sys import stdin, stdout
cin = stdin.readline
cout = stdout.write
mp = lambda : list(map(int, cin().split()))
(t,) = mp()
for _ in range(t):
	(n, k) = mp()
	ans = 0
	while n:
		if not n % k:
			ans += 1
			n //= k
		else:
			x = n % k
			ans += x
			n -= x
	cout(str(ans) + '\n')


def f(i):
	(n, k) = i
	if k > n:
		return n
	else:
		c = 0
		while n > 0:
			if n % k == 0:
				n //= k
				c += 1
			else:
				x = n % k
				n -= x
				c += x
		return c
l = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l.append((n, k))
ans = [f(i) for i in l]
for i in ans:
	print(i)


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


a = int(input())
for i in range(a):
	(b, c) = map(int, input().split())
	ans = 0
	while True:
		temp = b % c
		if temp == 0:
			ans += 1
			b = b // c
		elif temp != 0:
			ans += b % c
			b = b - b % c
		if b <= 0:
			break
	print(ans)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	ans = 0
	while N:
		ans += N % K
		if N < K:
			break
		N //= K
		ans += 1
	print(ans)


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


for i in range(int(input())):
	(num, k) = input().split()
	num = int(num)
	k = int(k)
	count = 0
	while num > 0:
		if num < k:
			count += num % k
			break
		count += num % k + 1
		num = num // k
	print(count)


def fn(n, k, ans):
	if n == 0:
		return ans
	d = n % k
	ans += d + 1
	n = n - d
	n = n // k
	return fn(n, k, ans)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(fn(n, k, 0) - 1)


n = int(input())
for i in range(n):
	a = list(map(int, input().split()))
	total = 0
	b = a[0]
	c = a[1]
	while b != 0:
		total += b % c + 1
		b //= c
	print(total - 1)


test = int(input())
for i in range(test):
	(N, K) = map(int, input().split())
	fuck_cnt = 0
	while N != 0:
		fuck_cnt += N % K + 1
		N = N // K
	print(fuck_cnt - 1)


tc = int(input())
while tc > 0:
	(n, k) = [int(i) for i in input().split()]
	cnt = 0
	while n != 0:
		if n % k != 0:
			cnt += n % k
			n -= n % k
		else:
			n //= k
			cnt += 1
	print(cnt)
	tc -= 1


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


def find_min(num, div):
	s = 0
	while num != 0:
		if num % div != 0:
			rem = num % div
			s += rem
			num -= rem
		else:
			num //= div
			s += 1
	return s
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().strip().split()))
	print(find_min(n, k))


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


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


from sys import stdin
from collections import defaultdict

def get_line(f=stdin):
	return f.readline().rstrip()

def get_int(f=stdin):
	return int(f.readline().rstrip())

def get_ints(f=stdin):
	return [int(x) for x in f.readline().rstrip().split(' ')]

def steps(n, k):
	if n < k:
		return n
	rem = n % k
	div = n // k
	return rem + 1 + steps(div, k)
t = get_int()
for _ in range(t):
	(n, k) = get_ints()
	print(steps(n, k))


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


for k in range(int(input())):
	nk = list(map(int, input().split()))
	step = 0
	while nk[0] != 0:
		if nk[0] % nk[1] == 0:
			nk[0] = int(nk[0] // nk[1])
			step += 1
		else:
			step += nk[0] % nk[1]
			nk[0] -= nk[0] % nk[1]
	print(step)


n = int(input())
for i in range(n):
	z = list(map(int, input().split()))
	k = z[1]
	count = 0
	while z[0] > 0:
		if z[0] % k == 0:
			z[0] //= k
			count += 1
		else:
			kevin = z[0] % k
			z[0] = z[0] - kevin
			count += kevin
	print(count)


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


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


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


from sys import stdin, stdout
from itertools import combinations
from collections import defaultdict, OrderedDict
import math
import heapq

def listIn():
	return list(map(int, stdin.readline().strip().split()))

def stringListIn():
	return [x for x in stdin.readline().split()]

def intIn():
	return int(stdin.readline())

def stringIn():
	return stdin.readline().strip()
for _ in range(intIn()):
	(n, k) = listIn()
	ans = 0
	while n > 0:
		m = n % k
		if m == 0:
			ans += 1
			n //= k
		else:
			ans += m
			n = n - m
	print(ans)


for t in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	ct = 0
	while n > 0:
		if n % k == 0:
			n = n // k
			ct += 1
		else:
			reduce = n // k * k
			ct += n - reduce
			n = reduce
	print(ct)


import sys
T = int(sys.stdin.readline().rstrip())
for t in range(T):
	(n, k) = map(int, sys.stdin.readline().rstrip().split())
	answer = 0
	while n > 0:
		r = n % k
		if r == 0:
			n //= k
			answer += 1
		else:
			n -= r
			answer += r
	print(answer)


from decimal import Decimal
t = int(input(''))
a = []
for i in range(t):
	(n, k) = input('').split()
	n = Decimal(n)
	k = Decimal(k)
	count = 0
	while n != 0:
		if n % k == 0:
			n /= k
			count += 1
		else:
			j = int(n / k)
			count += n - j * k
			n = j * k
	a.append(count)
for index in range(len(a)):
	print(int(a[index]))


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


t = int(input())
while t != 0:
	t = t - 1
	(n, k) = map(int, input().split(' '))
	stps = 0
	while n != 0:
		if n < k:
			stps = stps + n
			n = 0
		elif n % k == 0:
			n = n // k
			stps = stps + 1
		else:
			stps = stps + n % k + 1
			n = n // k
	print(stps)


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


t = int(input())
ans = []
for i in range(t):
	(n, k) = map(int, input().split())
	ans.append(0)
	while n > 0:
		ans[-1] += n % k + 1
		n //= k
	ans[-1] -= 1
print('\n'.join((str(i) for i in ans)))


import sys, math, queue, bisect
MOD = 10 ** 9 + 7
sys.setrecursionlimit(1000000)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	while n != 0:
		if n % k == 0:
			n = n // k
			ans += 1
		else:
			ans += n % k
			n = n - n % k
	print(ans)


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


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


def gcd(a, b):
	if b == 0:
		return a
	return b % a + 1 + gcd(b, a % b)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	sm = 0
	while a > 0:
		if a % b == 0:
			a = a // b
			sm += 1
		else:
			sm += a % b
			a = a // b * b
	print(sm)


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
nb_test = RI()
for _ in range(nb_test):
	(n, divs) = RMI()
	ans = 0
	while n > 0:
		(n, rest) = divmod(n, divs)
		ans += rest + (n > 0)
	print(ans)


import math
import bisect
import heapq
from collections import defaultdict

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, x, y) = egcd(b % a, a)
		return (g, y - b // a * x, x)

def mulinv(b, n):
	(g, x, _) = egcd(b, n)
	if g == 1:
		return x % n

def isprime(n):
	for d in range(2, int(math.sqrt(n)) + 1):
		if n % d == 0:
			return False
	return True

def argsort(ls):
	return sorted(range(len(ls)), key=ls.__getitem__)

def f(p=0):
	if p == 1:
		return map(int, input().split())
	elif p == 2:
		return list(map(int, input().split()))
	elif p == 3:
		return list(input())
	else:
		return int(input())

class DisjointSet:
	_disjoint_set = list()

	def __init__(self, init_arr):
		self._disjoint_set = []
		if init_arr:
			for item in list(set(init_arr)):
				self._disjoint_set.append([item])

	def _find_index(self, elem):
		for item in self._disjoint_set:
			if elem in item:
				return self._disjoint_set.index(item)
		return None

	def find(self, elem):
		for item in self._disjoint_set:
			if elem in item:
				return self._disjoint_set[self._disjoint_set.index(item)]
		return None

	def union(self, elem1, elem2):
		index_elem1 = self._find_index(elem1)
		index_elem2 = self._find_index(elem2)
		if index_elem1 != index_elem2 and index_elem1 is not None and (index_elem2 is not None):
			self._disjoint_set[index_elem2] = self._disjoint_set[index_elem2] + self._disjoint_set[index_elem1]
			del self._disjoint_set[index_elem1]
		return self._disjoint_set

	def get(self):
		return self._disjoint_set

def graph(n, m, edg=False):
	edges = []
	visited = [0] * n
	g = [list() for _ in range(n + 1)]
	for i in range(m):
		(u, v) = f(1)
		g[u].append(v)
		g[v].append(u)
		if edg:
			edges.append((u, v))
	if edg:
		return (g, visited, edg)
	else:
		return (g, visited)

def bfs(g, visited):
	queue = [1]
	visited[1] = 1
	for u in queue:
		for v in g[u]:
			if visited[v] == 0:
				queue.append(v)
			visited[v] = 1

def dfs(u, g, visited):
	print(u)
	visited[u] = 1
	for v in g[u]:
		if visited[v] == 0:
			dfs(v, g, visited)
t = f()
res = 0
for i in range(t):
	(n, k) = f(1)
	res = 0
	while n != 0:
		ost = n % k
		if ost == 0:
			n = n // k
			res += 1
		else:
			res += ost
			if n - ost == 0:
				break
			else:
				n = (n - ost) // k
				res += 1
	print(res)


def hero_to_zeroa(n: int, k: int) -> int:
	step = 0
	while n > 0:
		step += n % k
		n = n // k * k
		if n == 0:
			break
		step += 1
		n //= k
	return step
numtest = int(input().strip())
for _ in range(numtest):
	line = input().strip().split()
	print(hero_to_zeroa(int(line[0]), int(line[1])))


q = int(input())
while q > 0:
	q -= 1
	(a, b) = map(int, input().split())
	cnt = 0
	while a != 0:
		cnt += a % b
		if a >= b:
			cnt += 1
		a //= b
	print(cnt)


n = int(input())
while n > 0:
	x = input()
	(s, l) = x.split(' ')
	s = int(s)
	l = int(l)
	count = 0
	while s != 0:
		if s % l == 0:
			s = int(s // l)
			count = count + 1
		else:
			count = count + s % l
			s = s - s % l
	n = n - 1
	print(int(count))


t = [int(k) for k in input().split(' ')][0]
for nbt in range(t):
	(n, k) = [int(k) for k in input().split(' ')]
	res = 0
	while n != 0:
		res += n % k
		n -= n % k
		if n >= k:
			n //= k
			res += 1
	print(res)


from math import *
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	cnt = 0
	while n >= k:
		cnt += n % k + 1
		n //= k
	print(cnt + n % k)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	c = 0
	while n:
		c += n % k
		n -= n % k
		n = n // k
		c += 1
	print(c - 1)


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


from sys import stdin
from sys import stdout
t = int(stdin.readline())
while t != 0:
	c = 0
	(n, k) = stdin.readline().split()
	(n, k) = (int(n), int(k))
	while n != 0:
		c += n % k
		n //= k
		c += 1
	stdout.write(str(c - 1))
	stdout.write('\n')
	n -= 1
	t -= 1


from sys import stdin, setrecursionlimit
import heapq
import collections
import math

def brute(num, k, dp):
	steps = 0
	while True:
		if num == 0:
			break
		if num % k == 0:
			num = num // k
			steps += 1
			continue
		else:
			t = num % k
			num = num - t
			steps += t
	return steps
t = int(stdin.readline().strip())
for _ in range(t):
	dp = dict()
	(n, k) = list(map(int, stdin.readline().split()))
	print(brute(n, k, dp))


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


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


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


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


tests = int(input())
for t in range(tests):
	(n, k) = [int(x) for x in input().split(' ')]
	c = 0
	if n < k:
		print(n)
	else:
		while n:
			if n % k == 0:
				c += 1
				n //= k
			else:
				c += n % k
				n = n - n % k
		print(c)


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


t = int(input())
ans = []

def fun(n, k):
	if k == 1:
		return n
	i = 0
	while True:
		while n % k != 0:
			i = i + n % k
			n = n - n % k
		if n == 0:
			return i
		while n % k == 0:
			n = n // k
			i = i + 1
for i in range(t):
	(n, k) = input().split(' ')
	ans.append(fun(int(n), int(k)))
for i in range(len(ans)):
	print(ans[i])


import math
import collections
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	c = 0
	while n != 0:
		r = n % k
		c += r
		n = n - r
		if n != 0:
			n //= k
			c += 1
		else:
			break
	print(c)


t = int(input())
while t > 0:
	(n, k) = input().split()
	(n, k) = [int(n), int(k)]
	ct = 0
	while n > 0:
		if n % k == 0:
			n = n // k
			ct = ct + 1
		else:
			d = n % k
			n = n - d
			ct = ct + d
	print(ct)
	t = t - 1


x = int(input())
list_of_queries = []
for i in range(x):
	a = input()
	a = a.split()
	a[0] = int(a[0])
	a[1] = int(a[1])
	list_of_queries.append(a)
for i in list_of_queries:
	x = i[0]
	y = i[1]
	counter = 0
	while x > 0:
		if x % y != 0:
			counter += x % y + 1
			x = x // y
		else:
			counter += 1
			x = x // y
	print(counter - 1)


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


import sys
input = sys.stdin.readline
for zzz in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	while n != 0:
		divisible = n // k * k
		ans += n - divisible + 1
		n = divisible // k
	print(ans - 1)


def steps(n: int, k: int) -> int:
	steps = 0
	while n > 0:
		if not n % k:
			steps += 1
			n //= k
		else:
			steps += n % k
			n -= n % k
	return steps
N = int(input())
for i in range(N):
	nk = list(map(int, input().split()))
	(n, k) = (nk[0], nk[1])
	print(steps(n, k))


t = int(input())
for i in range(t):
	riga = input()
	n = int(riga.split()[0])
	k = int(riga.split()[1])
	step = 0
	while n > 0:
		r = n % k
		if r == 0:
			n //= k
			step += 1
		else:
			n -= r
			step += r
	print(step)


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


for n in range(int(input())):
	(a, b) = map(int, input().split())
	l = 0
	while 1:
		j = a // b * b
		l += a - j
		a = j // b
		l += 1
		if a == 0:
			break
	print(l - 1)


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


import math
from collections import deque, defaultdict
from sys import stdin, stdout
input = stdin.readline
listin = lambda : list(map(int, input().split()))
mapin = lambda : map(int, input().split())
for _ in range(int(input())):
	(n, k) = mapin()
	count = 0
	while True:
		if n % k:
			count += n % k
			n -= n % k
		else:
			while n % k == 0:
				n //= k
				count += 1
		if n == 0:
			print(count)
			break


num_queries = int(input())
list_queries = []
for i in range(num_queries):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	list = []
	list.append(n)
	list.append(k)
	list_queries.append(list)
for j in range(num_queries):
	count = 0
	while list_queries[j][0] != 0:
		count = count + list_queries[j][0] % list_queries[j][1] + 1
		list_queries[j][0] = int(list_queries[j][0] // list_queries[j][1])
	count = count - 1
	print(count)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	count = 0
	c = 0
	while a != 0:
		c = a % b
		count += c
		a -= c
		if a % b == 0:
			a = a // b
			count += 1
		c = 0
	print(count - 1)


import sys, os
f = lambda : list(map(int, input().split()))
if 'local' in os.environ:
	sys.stdin = open('./input.txt', 'r')

def solve():
	t = f()[0]
	for i in range(t):
		(n, k) = f()
		cnt = 0
		while n:
			if n % k == 0:
				n = n // k
				cnt += 1
			else:
				minus = n % k
				n -= minus
				cnt += minus
		print(cnt)
solve()


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


t = int(input())
kq = []
for i in range(0, t):
	kq.append(0)
	nk = input()
	nk = nk.split()
	nk[1] = eval(nk[1])
	nk[0] = eval(nk[0])
	while nk[0] != 0:
		if nk[0] % nk[1] == 0:
			nk[0] = nk[0] // nk[1]
			kq[i] = kq[i] + 1
		else:
			a = nk[0] % nk[1]
			nk[0] = nk[0] - a
			kq[i] = kq[i] + a
for i in range(0, t):
	print(round(kq[i], 0))


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


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


x = int(input())
i = 0
t = 0
for j in range(x):
	(a, b) = map(int, input().split())
	i = 0
	while True:
		if a == 0:
			break
		elif a % b == 0:
			a = a // b
			i = i + 1
		else:
			t = a % b
			a = a - t
			i = i + t
	print(i)


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


q = int(input())
while q > 0:
	(n, k) = map(int, input().split())
	total = 0
	while n != 0:
		if n % k:
			total += n % k
			n -= n % k
		else:
			n //= k
			total += 1
	q -= 1
	print(total)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

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

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(''.join([str(x) for x in a]) + '\n')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = 1
t = int(input())
for _ in range(t):
	(n, k) = li()
	i = 0
	while n > 0:
		if n % k == 0:
			n //= k
			i += 1
		else:
			i += n % k
			n -= n % k
	print(i)


n = int(input())
for j in range(n):
	a = 0
	ls = input().split()
	ls[0] = int(ls[0])
	ls[1] = int(ls[1])
	while ls[0] != 0:
		b = int(ls[0] % ls[1])
		if b == 0:
			a = a + 1
			ls[0] = ls[0] // ls[1]
		else:
			ls[0] = ls[0] - b
			a = a + b
	print(a)


a = int(input())
for _ in range(a):
	b = input().split()
	amount = int(b[0])
	j = 0
	while amount != 0:
		j = j + amount % int(b[1]) + 1
		amount = amount // int(b[1])
	print(j - 1)


import sys, math

def read_int():
	return int(sys.stdin.readline().strip())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def read_string():
	return sys.stdin.readline().strip()

def read_string_list(delim=' '):
	return sys.stdin.readline().strip().split(delim)
t = read_int()
for _ in range(t):
	(n, k) = read_int_list()
	counter = 0
	while n > 0:
		mod = n % k
		if mod != 0:
			n -= mod
			counter += mod
		else:
			n = n // k
			counter += 1
	print(counter)