In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem.  
$\left(\begin{matrix}n\\ k\end{matrix}\right)$
denotes the number of ways of choosing k objects from n different objects.

However when n and k are too large, we often save them after modulo operation by a prime number P. Please calculate how many binomial coefficients of n become to 0 after modulo by P.

Input Format 

The first of input is an integer ${T}$, the number of test cases. 

Each of the following ${T}$ lines contains 2 integers, $n$ and prime ${P}$.  

Constraints 

$T<100$ 

$n<10^{500}$ 

$P<10^9$

Output Format

For each test case, output a line contains the number of   $\left(\begin{matrix}n\\ k\end{matrix}\right)$s (0<=k<=n)  each of which after modulo operation by P is 0.

Sample Input

3
2 2
3 2
4 3

Sample Output

1
0
1

Difficulty: MEDIUM
Tags: Number theory

Starter code:

Solutions:
def solve(n, p):
	a = []
	nn = n
	while nn > 0:
		a.append(nn % p)
		nn //= p
	m = 0
	for i in range(len(a)):
		b = a[-(i + 1)]
		m *= b + 1
		m += b
	print(n - m)
t = int(input())
for i in range(t):
	(n, p) = [int(j) for j in input().split(' ')]
	solve(n, p)


import sys
T = int(sys.stdin.readline())
for i in range(T):
	(n, P) = list(map(int, sys.stdin.readline().split(' ')))
	m = n
	k = 1
	while m > 0:
		k *= m % P + 1
		m //= P
	print(n + 1 - k)


def func(n, p):
	tmp = n
	baseK = []
	while n:
		baseK.append(n % p)
		n = n // p
	result = 1
	for i in baseK:
		result *= i + 1
	return tmp + 1 - result

def hackerrank():
	for t in range(int(input())):
		(n, p) = (int(i) for i in input().split())
		print(func(n, p))
hackerrank()


T = int(input())
for i in range(T):
	(n, p) = [int(j) for j in input().split()]
	curr = n
	count = 1
	while curr > 0:
		count *= curr % p + 1
		curr //= p
	print(n + 1 - count)


def divisibleCoefficients(n: int, p: int) -> int:
	(m, nondiv) = (n, 1)
	while m > 0:
		nondiv = nondiv * (m % p + 1)
		m = m // p
	return n + 1 - nondiv
t = int(input())
for test in range(t):
	(n, p) = (int(i) for i in input().strip().split())
	print(divisibleCoefficients(n, p))


import sys

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		(n, p) = (int(i) for i in sys.stdin.readline().split())
		print(divisibleCoefficients(n, p))

def divisibleCoefficients(n, p):
	(m, nondiv) = (n, 1)
	while m > 0:
		nondiv *= m % p + 1
		m //= p
	return n + 1 - nondiv
main()


t = int(input())
for i in range(t):
	s = input().strip().split()
	n = int(s[0])
	p = int(s[1])
	if n == p:
		print(n - 1)
	else:
		notp = 1
		q = n
		while q != 0:
			r = q % p
			notp *= r + 1
			q = q // p
		print(n + 1 - notp)


def solve(n, P):
	(c, n_) = (1, n)
	while n_ > 0:
		(n_, d) = divmod(n_, P)
		c *= d + 1
	return n + 1 - c
T = int(input())
for _ in range(T):
	(n, P) = (int(_) for _ in input().split())
	print(solve(n, P))


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


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


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


t = int(input())
for i in range(0, t):
	line = input()
	nums = line.split(' ')
	N = int(nums[0])
	P = int(nums[1])
	digits = []
	while N:
		digits.append(N % P)
		N = N // P
	n = len(digits)
	prods = []
	powers = []
	powers.append(1)
	last = 1
	for i in range(0, n):
		last *= digits[i] + 1
		prods.append(last)
	last = 1
	for i in range(1, n):
		last *= P
		powers.append(last)
	ans = 0
	for i in range(n - 1, 0, -1):
		ans += digits[i] * (powers[i] - prods[i - 1])
	print(ans)


from functools import reduce
from operator import mul

def digits(n, p):
	result = []
	while n:
		(n, digit) = divmod(n, p)
		result.append(digit)
	return result
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	print(n + 1 - reduce(mul, [d + 1 for d in digits(n, p)], 1))


T = int(input().strip())
for i in range(T):
	(n, P) = [int(x) for x in input().strip().split(' ')]
	t = n
	m = 1
	while t:
		m = m * (t % P + 1)
		t = t // P
	m = n - m + 1
	print(m)


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


tests = int(input())

def solve(n, p):
	total = n + 1
	num_valid = 1
	while n != 0:
		ni = n % p
		n = n // p
		num_valid *= ni + 1
	return total - num_valid
for t in range(0, tests):
	(n, p) = map(int, input().split())
	ans = solve(n, p)
	print(ans)


T = int(input())
ans = []
for _ in range(T):
	(n, P) = list(map(int, input().split()))
	m = n
	k = 1
	while m > 0:
		k *= m % P + 1
		m //= P
	ans.append(n + 1 - k)
for i in range(len(ans)):
	print(ans[i])


def f(n, p):
	ans = 1
	while n:
		a = n % p
		ans *= a + 1
		n //= p
	return ans
T = int(input().strip())
for _ in range(T):
	(N, P) = map(int, input().strip().split(' '))
	print(N + 1 - f(N, P))


t = int(input())
for i in range(t):
	(n, p) = [int(x) for x in input().split(' ')]
	prod = 1
	initial = n
	while n > 0:
		rem = n % p
		prod *= rem + 1
		if prod == 0:
			break
		n = n // p
	print(initial + 1 - prod)


t = int(input().strip())
while t > 0:
	t -= 1
	(n, p) = [int(x) for x in input().strip().split()]
	tmp = n
	num_digits = 0
	a = []
	while n != 0:
		a.append(n % p)
		n //= p
	count = len(a)
	ret = 0
	prod = a[0] + 1
	power = p
	for i in range(1, count):
		ret += (power - prod) * a[i]
		prod *= a[i] + 1
		power *= p
	print(ret)


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	(res, d) = (n + 1, 1)
	while n > 0:
		d *= n % p + 1
		n //= p
	print(res - d)


T = int(input())
for t in range(T):
	(n, p) = map(int, input().split())
	m = n
	nonzero = 1
	while m:
		nonzero *= m % p + 1
		m //= p
	print(n + 1 - nonzero)


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	s = 1
	nn = n
	t = 1
	while n:
		s = s * (n % p + 1)
		n //= p
		t *= p
	print(t - s - (t - 1 - nn))


def count_zero(n, p):
	old_n = n
	nonzero = 1
	while n > 0:
		nonzero *= n % p + 1
		n //= p
	return old_n + 1 - nonzero
T = int(input())
for t in range(T):
	(N, P) = map(int, input().split())
	print(count_zero(N, P))


def cal_non(n, p):
	res = 1
	while n:
		res *= n % p + 1
		n //= p
	return res
for _ in range(int(input())):
	(n, p) = [int(x) for x in input().split()]
	non = cal_non(n, p)
	print(n + 1 - non)


T = int(input())
for _ in range(0, T):
	(n, p) = [int(a) for a in input().split()]
	L = []
	while n > 0:
		L.append(n % p)
		n //= p
	total_sum = 0
	for a in range(0, len(L)):
		for b in range(a + 1, len(L)):
			top_prod = 1
			mid_prod = 1
			low_prod = 1
			after_digits = pow(p, a)
			for i in range(0, a):
				low_prod *= L[i] + 1
			for i in range(a + 1, b):
				mid_prod *= L[i] + 1
			top_prod *= L[b]
			total_sum += top_prod * mid_prod * (p - 1 - L[a]) * after_digits
	print(total_sum)


import sys
from collections import deque
from time import time

def pascal_gen(m):
	row = deque([1])
	while True:
		yield row
		new_row = deque()
		for i in range(1, len(row)):
			new_row.append((row[i - 1] + row[i]) % m)
		new_row.appendleft(1)
		new_row.append(1)
		row = new_row

def solve_bf(n, m):
	print('n=%d m=%d' % (n, m), file=sys.stderr)
	for (i, row) in enumerate(pascal_gen(m)):
		c = row.count(0)
		print('i=%3d zeros=%3d nonzeros=%3d' % (i, c, len(row) - c), file=sys.stderr)
		if i == n:
			return row.count(0)
	return None

def rdd_gen(n, p):
	if n == 0:
		yield 0
	while n:
		yield (n % p)
		n //= p

def solve(n, p):
	print('p=%d' % (p,), file=sys.stderr)
	cnt = 1
	for a in rdd_gen(n, p):
		cnt *= a + 1
	print('cnt=%d' % cnt, file=sys.stderr)
	return n + 1 - cnt
tm = time()
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(solve(n, m))
print('time elapsed: %s' % (time() - tm), file=sys.stderr)


t = int(input())
for i in range(t):
	ins = input().split(' ')
	n = int(ins[0])
	p = int(ins[1])
	ans = n + 1
	nonans = 1
	while n > 0:
		nonans = nonans * (n % p + 1)
		n = n // p
	ans = ans - nonans
	print(ans)


import sys
t = int(input())
i = 0
while i < t:
	i += 1
	(n, p) = input().split()
	n = int(n)
	N = n
	p = int(p)
	ans = 1
	while n:
		res = n % p
		ans = ans * (res + 1)
		n //= p
	print(N + 1 - ans)


import math
import itertools
numCases = int(input())
for i in range(numCases):
	[n, p] = map(int, input().split())
	numVanishing = n + 1
	numNonVanishing = 1
	while n > 0:
		numNonVanishing *= 1 + n % p
		n //= p
	numVanishing -= numNonVanishing
	print(numVanishing)


import os
import sys

def solve(n, p):
	a = 1
	np1 = n + 1
	while n >= p:
		(n, r) = divmod(n, p)
		a *= r + 1
	a *= n + 1
	a = np1 - a
	print(a)
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	solve(n, p)


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


def cal(n, p):
	a = []
	nn = n
	while nn > 0:
		a.append(nn % p)
		nn //= p
	m = 0
	for j in range(len(a)):
		b = a[-(j + 1)]
		m *= b + 1
		m += b
	print(n - m)
t = int(input())
for i in range(t):
	(n, p) = [int(j) for j in input().split(' ')]
	cal(n, p)


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


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


for _ in range(int(input())):
	(N, P) = [int(i) for i in input().split()]
	if N == P:
		print(N - 1)
	elif N < P:
		print(0)
	else:
		prod = 1
		n = N
		while n:
			prod = prod * (n % P + 1)
			n = n // P
		print(N + 1 - prod)


import os
import sys

def solve(n, p):
	a = 1
	n1 = n + 1
	while n >= p:
		(n, r) = divmod(n, p)
		a *= r + 1
	a *= n + 1
	a = n1 - a
	print(a)
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	solve(n, p)


T = int(input())
for _ in range(T):
	(N, P) = map(int, input().split())
	n = N
	non0 = 1
	while n:
		(n, d) = divmod(n, P)
		non0 *= d + 1
	print(N + 1 - non0)


def solve(n, p):
	a = 1
	n1 = n + 1
	while n >= p:
		(n, r) = divmod(n, p)
		a *= r + 1
	a *= n + 1
	a = n1 - a
	print(a)
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	solve(n, p)


for t in range(int(input())):
	(n, p) = map(int, input().split())
	res = 0
	mult = 1
	while n >= p:
		rm = n % p + 1
		n //= p
		res += mult * (p - rm) * n
		mult *= rm
	print(int(res))


def solve(n, p):
	a = 1
	n1 = n + 1
	while n >= p:
		(n, r) = divmod(n, p)
		a *= r + 1
	a *= n + 1
	a = n1 - a
	print(a)
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	solve(n, p)


def solve(n, p):
	a = 1
	n1 = n + 1
	while n >= p:
		(n, r) = divmod(n, p)
		a *= r + 1
	a *= n + 1
	a = n1 - a
	print(a)
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	solve(n, p)


t = int(input())
for i in range(t):
	(n, p) = [int(x) for x in input().split(' ')]
	prod = 1
	initial = n
	while n > 0:
		rem = n % p
		prod *= rem + 1
		if prod == 0:
			break
		n = n // p
	print(initial + 1 - prod)


T = int(input())
ans = []
for _ in range(T):
	(n, P) = list(map(int, input().split()))
	m = n
	k = 1
	while m > 0:
		k *= m % P + 1
		m //= P
	ans.append(n + 1 - k)
for i in range(len(ans)):
	print(ans[i])


def basep_plusone(n, p):
	while n >= p:
		yield (n % p + 1)
		n //= p
	yield (n + 1)

def prod(gen):
	ret = 1
	for x in gen:
		ret *= x
	return ret

def solve(n, p):
	num_le = prod(basep_plusone(n, p))
	return n - num_le + 1
t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	result = solve(n, p)
	print(result)


def solve(n, p):
	res = 1
	total = n + 1
	while n > 0:
		r = n % p
		n = n // p
		if r != 0:
			res *= r + 1
	return total - res
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	print(solve(n, p))


import os
import sys

def Solve(n, p):
	total = n + 1
	res = 1
	while n > 0:
		res *= n % p + 1
		n //= p
	return total - res
for i in range(int(input())):
	(n, p) = map(int, input().split())
	ans = Solve(n, p)
	print(ans)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


def solve(n, p):
	a = 1
	n1 = n + 1
	while n >= p:
		(n, r) = divmod(n, p)
		a *= r + 1
	a *= n + 1
	a = n1 - a
	print(a)
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	solve(n, p)


import math
import os
import random
import re
import sys
from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


def solve(n, p):
	a = []
	nn = n
	while nn > 0:
		a.append(nn % p)
		nn //= p
	m = 0
	for i in range(len(a)):
		b = a[-(i + 1)]
		m *= b + 1
		m += b
	print(n - m)
t = int(input())
for i in range(t):
	(n, p) = [int(j) for j in input().split(' ')]
	solve(n, p)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)


from functools import reduce

def baseconv(n, b):
	newbase = []
	if n < b:
		return 0
	if n == b:
		return [1]
	while True:
		r = n % b
		newbase.insert(0, r)
		n = n // b
		if n == 0:
			break
	return newbase
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	base = baseconv(n, p)
	nonzeros = reduce(lambda x, y: x * y, (z + 1 for z in base))
	print(n - nonzeros + 1)