The binomial coefficient C(N, K) is defined as
N! / K! / (N − K)! for 0 ≤ K ≤ N. 

Here N! = 1 * 2 * ... * N for N ≥ 1, and 0! = 1.

You are given a prime number P and a positive integer N. 

A_{L} is defined as the number of elements in the sequence C(N, K), such that, P^{L} divides C(N, K),
but P^{L+1} does not divide C(N, K). Here, 0 ≤ K ≤ N.

Let M be an integer, such that, A_{M} > 0,
but A_{L} = 0 for all L > M.
Your task is to find numbers A_{0}, A_{1}, ..., A_{M}.

Input Format 

The first line of the input contains an integer T, denoting the number of test cases.
The description of T test cases follows.
The only line of each test case contains two space-separated integers N and P.

Output Format 

For each test case, display M + 1 space separated integers
A_{0}, A_{1}, ..., A_{M}
on the separate line.

Constraints

1 ≤ T ≤ 100 

1 ≤ N ≤ 10^{18} 

2 ≤ P < 10^{18} 

P is prime  

Sample Input

3
4 5
6 3
10 2

Sample Output

5
3 4
4 4 1 2

Explanation  

Example case 1. Values C(4, K) are {1, 4, 6, 4, 1}.
Each of them is not divisible by 5.
Therefore, A_{0} = 5, A_{1} = 0, A_{2} = 0, ..., hence the answer.

Example case 2. Values C(6, K) are {1, 6, 15, 20, 15, 6, 1}.
Among them 1, 20, 1 are not divisible by 3,
while remaining values 6, 15, 15, 6 are divisible by 3, but not divisible by 9.
Therefore, A_{0} = 3, A_{1} = 4,
A_{2} = 0, A_{3} = 0, ..., hence the answer.

Example case 3. Values C(10, K) are {1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1}.
Among them 1, 45, 45, 1 are not divisible by 2,
values 10, 210, 210, 10 are divisible by 2, but not divisible by 4,
value 252 is divisible by 4, but not divisible by 8,
finally, values 120, 120 are divisible by 8, but not divisible by 16.
Therefore, A_{0} = 4, A_{1} = 4,
A_{2} = 1, A_{3} = 2,
A_{4} = 0, A_{5} = 0, ..., hence the answer.

Source: hackerrank | Difficulty: MEDIUM
Tags: Combinatorics


Solutions:
from collections import Counter

def main():
	ncases = int(input())
	for _ in range(ncases):
		(n, p) = [int(fld) for fld in input().split()]
		m = count(n, p)
		print(' '.join(map(str, m)))

def count(n, p):
	d = []
	nn = n
	while nn != 0:
		d.append(nn % p)
		nn //= p
	pprev = Counter()
	nprev = Counter([0])
	for di in d:
		ncur = Counter({k: di * v for (k, v) in pprev.items()}) + Counter({k: (di + 1) * v for (k, v) in nprev.items()})
		pcur = Counter({k + 1: (p - di) * v for (k, v) in pprev.items()}) + Counter({k + 1: (p - di - 1) * v for (k, v) in nprev.items()})
		(pprev, nprev) = (pcur, ncur)
	return [ncur[i] for i in range(1 + max(ncur.keys()))]

def oldcount(n, p):
	m = Counter()
	for k in range(n + 1):
		m[factorcount(comb(n, k), p)] += 1
	return [m[i] for i in range(1 + max(m.keys()))]

def comb(n, k):
	assert 0 <= k <= n
	ans = 1
	for i in range(k):
		ans = ans * (n - i) // (i + 1)
	return ans

def factorcount(x, p):
	assert x > 0
	ans = 0
	while x % p == 0:
		ans += 1
		x //= p
	return ans
main()


from collections import Counter

def main():
	ncases = int(input())
	for _ in range(ncases):
		(n, p) = [int(fld) for fld in input().split()]
		m = count(n, p)
		print(' '.join(map(str, m)))

def count(n, p):
	d = []
	nn = n
	while nn != 0:
		d.append(nn % p)
		nn //= p
	pprev = Counter()
	nprev = Counter([0])
	for di in d:
		ncur = Counter({k: di * v for (k, v) in pprev.items()}) + Counter({k: (di + 1) * v for (k, v) in nprev.items()})
		pcur = Counter({k + 1: (p - di) * v for (k, v) in pprev.items()}) + Counter({k + 1: (p - di - 1) * v for (k, v) in nprev.items()})
		(pprev, nprev) = (pcur, ncur)
	return [ncur[i] for i in range(1 + max(ncur.keys()))]

def oldcount(n, p):
	m = Counter()
	for k in range(n + 1):
		m[factorcount(comb(n, k), p)] += 1
	return [m[i] for i in range(1 + max(m.keys()))]

def comb(n, k):
	assert 0 <= k <= n
	ans = 1
	for i in range(k):
		ans = ans * (n - i) // (i + 1)
	return ans

def factorcount(x, p):
	assert x > 0
	ans = 0
	while x % p == 0:
		ans += 1
		x //= p
	return ans
main()


from collections import Counter

def main():
	ncases = int(input())
	for _ in range(ncases):
		(n, p) = [int(fld) for fld in input().split()]
		m = count(n, p)
		print(' '.join(map(str, m)))

def count(n, p):
	d = []
	nn = n
	while nn != 0:
		d.append(nn % p)
		nn //= p
	pprev = Counter()
	nprev = Counter([0])
	for di in d:
		ncur = Counter({k: di * v for (k, v) in pprev.items()}) + Counter({k: (di + 1) * v for (k, v) in nprev.items()})
		pcur = Counter({k + 1: (p - di) * v for (k, v) in pprev.items()}) + Counter({k + 1: (p - di - 1) * v for (k, v) in nprev.items()})
		(pprev, nprev) = (pcur, ncur)
	return [ncur[i] for i in range(1 + max(ncur.keys()))]

def oldcount(n, p):
	m = Counter()
	for k in range(n + 1):
		m[factorcount(comb(n, k), p)] += 1
	return [m[i] for i in range(1 + max(m.keys()))]

def comb(n, k):
	assert 0 <= k <= n
	ans = 1
	for i in range(k):
		ans = ans * (n - i) // (i + 1)
	return ans

def factorcount(x, p):
	assert x > 0
	ans = 0
	while x % p == 0:
		ans += 1
		x //= p
	return ans
main()


t = int(input())
for _ in range(t):
	[n, p] = list(map(int, input().split()))
	numwcarry = [0]
	numwocarry = [1]
	dig = 0
	curr = n
	while curr > 0:
		nextwcarry = [0] * (dig + 2)
		nextwocarry = [0] * (dig + 2)
		currdig = curr % p
		for i in range(dig + 1):
			nextwocarry[i] = numwcarry[i] * currdig + numwocarry[i] * (currdig + 1)
			nextwcarry[i + 1] = numwcarry[i] * (p - currdig) + numwocarry[i] * (p - currdig - 1)
		numwocarry = nextwocarry
		numwcarry = nextwcarry
		curr //= p
		dig += 1
	toprint = numwocarry.copy()
	while len(toprint) > 0 and toprint[-1] == 0:
		toprint.pop()
	print(' '.join(list(map(str, toprint))))


from collections import Counter

def main():
	ncases = int(input())
	for _ in range(ncases):
		(n, p) = [int(fld) for fld in input().split()]
		m = count(n, p)
		print(' '.join(map(str, m)))

def count(n, p):
	d = []
	nn = n
	while nn != 0:
		d.append(nn % p)
		nn //= p
	pprev = Counter()
	nprev = Counter([0])
	for di in d:
		ncur = Counter({k: di * v for (k, v) in pprev.items()}) + Counter({k: (di + 1) * v for (k, v) in nprev.items()})
		pcur = Counter({k + 1: (p - di) * v for (k, v) in pprev.items()}) + Counter({k + 1: (p - di - 1) * v for (k, v) in nprev.items()})
		(pprev, nprev) = (pcur, ncur)
	return [ncur[i] for i in range(1 + max(ncur.keys()))]

def oldcount(n, p):
	m = Counter()
	for k in range(n + 1):
		m[factorcount(comb(n, k), p)] += 1
	return [m[i] for i in range(1 + max(m.keys()))]

def comb(n, k):
	assert 0 <= k <= n
	ans = 1
	for i in range(k):
		ans = ans * (n - i) // (i + 1)
	return ans

def factorcount(x, p):
	assert x > 0
	ans = 0
	while x % p == 0:
		ans += 1
		x //= p
	return ans
main()


def A(N, P):
	left = [[0] * 61, [0] * 61]
	right = [[0] * 61, [0] * 61]
	(i, j) = (0, 1)
	k = 1
	left[i][0] = 1
	while P ** (k - 1) <= N:
		Nk = N // P ** (k - 1) % P
		right[j][0] = 0
		for m in range(k):
			left[j][m] = left[i][m] * (Nk + 1) + right[i][m] * Nk
			right[j][m + 1] = left[i][m] * (P - 1 - Nk) + right[i][m] * (P - Nk)
		(i, j) = (j, i)
		k += 1
	m = len(left[i])
	while not left[i][m - 1]:
		m -= 1
	return left[i][:m]
T = int(input())
for _ in range(T):
	(N, P) = map(int, input().split())
	As = A(N, P)
	print(' '.join(map(str, As)))


from collections import Counter

def main():
	ncases = int(input())
	for _ in range(ncases):
		(n, p) = [int(fld) for fld in input().split()]
		m = count(n, p)
		print(' '.join(map(str, m)))

def count(n, p):
	d = []
	nn = n
	while nn != 0:
		d.append(nn % p)
		nn //= p
	pprev = Counter()
	nprev = Counter([0])
	for di in d:
		ncur = Counter({k: di * v for (k, v) in pprev.items()}) + Counter({k: (di + 1) * v for (k, v) in nprev.items()})
		pcur = Counter({k + 1: (p - di) * v for (k, v) in pprev.items()}) + Counter({k + 1: (p - di - 1) * v for (k, v) in nprev.items()})
		(pprev, nprev) = (pcur, ncur)
	return [ncur[i] for i in range(1 + max(ncur.keys()))]

def oldcount(n, p):
	m = Counter()
	for k in range(n + 1):
		m[factorcount(comb(n, k), p)] += 1
	return [m[i] for i in range(1 + max(m.keys()))]

def comb(n, k):
	assert 0 <= k <= n
	ans = 1
	for i in range(k):
		ans = ans * (n - i) // (i + 1)
	return ans

def factorcount(x, p):
	assert x > 0
	ans = 0
	while x % p == 0:
		ans += 1
		x //= p
	return ans
main()


from collections import Counter

def main():
	ncases = int(input())
	for _ in range(ncases):
		(n, p) = [int(fld) for fld in input().split()]
		m = count(n, p)
		print(' '.join(map(str, m)))

def count(n, p):
	d = []
	nn = n
	while nn != 0:
		d.append(nn % p)
		nn //= p
	pprev = Counter()
	nprev = Counter([0])
	for di in d:
		ncur = Counter({k: di * v for (k, v) in pprev.items()}) + Counter({k: (di + 1) * v for (k, v) in nprev.items()})
		pcur = Counter({k + 1: (p - di) * v for (k, v) in pprev.items()}) + Counter({k + 1: (p - di - 1) * v for (k, v) in nprev.items()})
		(pprev, nprev) = (pcur, ncur)
	return [ncur[i] for i in range(1 + max(ncur.keys()))]

def oldcount(n, p):
	m = Counter()
	for k in range(n + 1):
		m[factorcount(comb(n, k), p)] += 1
	return [m[i] for i in range(1 + max(m.keys()))]

def comb(n, k):
	assert 0 <= k <= n
	ans = 1
	for i in range(k):
		ans = ans * (n - i) // (i + 1)
	return ans

def factorcount(x, p):
	assert x > 0
	ans = 0
	while x % p == 0:
		ans += 1
		x //= p
	return ans
main()


from collections import Counter

def main():
	ncases = int(input())
	for _ in range(ncases):
		(n, p) = [int(fld) for fld in input().split()]
		m = count(n, p)
		print(' '.join(map(str, m)))

def count(n, p):
	d = []
	nn = n
	while nn != 0:
		d.append(nn % p)
		nn //= p
	pprev = Counter()
	nprev = Counter([0])
	for di in d:
		ncur = Counter({k: di * v for (k, v) in pprev.items()}) + Counter({k: (di + 1) * v for (k, v) in nprev.items()})
		pcur = Counter({k + 1: (p - di) * v for (k, v) in pprev.items()}) + Counter({k + 1: (p - di - 1) * v for (k, v) in nprev.items()})
		(pprev, nprev) = (pcur, ncur)
	return [ncur[i] for i in range(1 + max(ncur.keys()))]

def oldcount(n, p):
	m = Counter()
	for k in range(n + 1):
		m[factorcount(comb(n, k), p)] += 1
	return [m[i] for i in range(1 + max(m.keys()))]

def comb(n, k):
	assert 0 <= k <= n
	ans = 1
	for i in range(k):
		ans = ans * (n - i) // (i + 1)
	return ans

def factorcount(x, p):
	assert x > 0
	ans = 0
	while x % p == 0:
		ans += 1
		x //= p
	return ans
main()


from collections import Counter

def main():
	ncases = int(input())
	for _ in range(ncases):
		(n, p) = [int(fld) for fld in input().split()]
		m = count(n, p)
		print(' '.join(map(str, m)))

def count(n, p):
	d = []
	nn = n
	while nn != 0:
		d.append(nn % p)
		nn //= p
	pprev = Counter()
	nprev = Counter([0])
	for di in d:
		ncur = Counter({k: di * v for (k, v) in pprev.items()}) + Counter({k: (di + 1) * v for (k, v) in nprev.items()})
		pcur = Counter({k + 1: (p - di) * v for (k, v) in pprev.items()}) + Counter({k + 1: (p - di - 1) * v for (k, v) in nprev.items()})
		(pprev, nprev) = (pcur, ncur)
	return [ncur[i] for i in range(1 + max(ncur.keys()))]

def oldcount(n, p):
	m = Counter()
	for k in range(n + 1):
		m[factorcount(comb(n, k), p)] += 1
	return [m[i] for i in range(1 + max(m.keys()))]

def comb(n, k):
	assert 0 <= k <= n
	ans = 1
	for i in range(k):
		ans = ans * (n - i) // (i + 1)
	return ans

def factorcount(x, p):
	assert x > 0
	ans = 0
	while x % p == 0:
		ans += 1
		x //= p
	return ans
main()