Chef wants to select a subset $S$ of the set $\{1, 2, \ldots, N\}$ such that there are no two integers $x, y \in S$ which satisfy $\frac{x}{y} = M$.
Help Chef find the maximum size of a subset $S$ he can choose and the number of ways in which he can choose a subset $S$ with this maximum size. Since the number of ways to choose $S$ can be very large, calculate it modulo $998,244,353$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $M$.

-----Output-----
For each test case, print a single line containing two space-separated integers ― the maximum size of a subset Chef can choose and the number of ways to choose a subset with this maximum size modulo $998,244,353$. Note that only the number of ways to choose a subset should be printed modulo $998,244,353$.

-----Constraints-----
- $1 \le T \le 10,000$
- $2 \le M \le N \le 10^{18}$

-----Example Input-----
3
5 2
10 2
100 3

-----Example Output-----
4 1
6 12
76 49152

-----Explanation-----
Example case 1: The only subset $S$ with the maximum size which Chef can choose is $\{1, 3, 4, 5\}$.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Mathematics


Solutions:
def groupsInInterval(L, R, M, N):
	if R <= N:
		return R - (L - 1) - (R // M - (L - 1) // M)
	else:
		return 0

def power(a, b):
	MOD = 998244353
	res = 1
	while b > 0:
		if b % 2:
			res *= a
			res %= MOD
		b //= 2
		a *= a
		a %= MOD
	return res
while True:
	try:
		test = int(input())
	except EOFError:
		break
	for i in range(test):
		MOD = 998244353
		(n, m) = map(int, input().split())
		(taken, ways) = (0, 1)
		for i in range(1, 70):
			L = n // m ** i + 1
			R = n // m ** (i - 1)
			groups = groupsInInterval(L, R, m, n)
			if i % 2 == 0:
				taken += i // 2 * groups
				ways *= power(i // 2 + 1, groups)
			else:
				taken += (i + 1) // 2 * groups
				ways *= 1
		print(taken, ways % MOD)


def help():
	(n, m) = map(int, input().split(' '))
	max_power = 0
	n1 = n
	while n1 >= m:
		n1 = n1 // m
		max_power += 1
	sizes = [0] * (max_power + 1)
	sizes[max_power] = n // m ** max_power
	yet = sizes[max_power]
	curr = max_power - 1
	while curr >= 0:
		y1 = n // m ** curr
		sizes[curr] = y1 - yet
		yet = y1
		curr -= 1
	size = [0] * (max_power + 1)
	for i in range(max_power, -1, -1):
		curr = sizes[i]
		size[i] = curr
		for j in range(max_power + 1):
			sizes[j] -= curr
	size_ans = 0
	ways_ans = 1
	for i in range(max_power + 1):
		C = i + 1
		size_ans += size[i] * ((C + 1) // 2)
		if C % 2 == 0:
			ways_ans *= pow(C // 2 + 1, size[i], 998244353)
			ways_ans = ways_ans % 998244353
	print(size_ans, ways_ans)
for _ in range(int(input())):
	help()


ts = int(input())
for _ in range(ts):
	(n, m) = map(int, input().split())
	(t, tt, res, cnt) = (1, [], 0, 1)
	while t <= n:
		t *= m
		v = n // t
		v -= v // m
		if tt:
			tt[-1] -= v
		tt.append(v)
	for (i, v) in enumerate(tt):
		res += (i + 2) // 2 * v
		if i & 1 == 0:
			cnt = cnt * pow((i + 2) // 2 + 1, v, 998244353) % 998244353
	print(n - res, cnt)


import sys
input = sys.stdin.readline
(inp, ip) = (lambda : int(input()), lambda : [int(w) for w in input().split()])
M = 998244353
for _ in range(inp()):
	(n, m) = ip()
	(size, ways) = (0, 1)
	(a, b) = (1, m)
	for k in range(1, 70):
		if a > n:
			break
		ct = n // a - n // b - (n // a // m - n // b // m)
		size += ct * ((1 + k) // 2)
		if k % 2 == 0:
			ways = ways * pow(k // 2 + 1, ct, M) % M
		(a, b) = (a * m, b * m)
	print(size, ways)


import sys
sys.setrecursionlimit(10 ** 9)
mod = 998244353

def power(a, b):
	res = 1
	while b > 0:
		if b % 2:
			res *= a
			res %= mod
		b //= 2
		a *= a
		a %= mod
	return res

def solve(a):
	if a > n:
		return (0, 1)
	val = a
	c = 1
	p = 1
	size = 0
	ways = 0
	while 1:
		if val > n // m:
			break
		val *= m
		p *= m
		c += 1
	u = n // p
	ans = solve(u + 1)
	rem = u // m
	rem -= (a - 1) // m
	u -= rem
	size = (c + 1) // 2 * (u - a + 1)
	if c % 2:
		ways = 1
	else:
		ways = power(c // 2 + 1, u - a + 1)
	size += ans[0]
	ways *= ans[1]
	ways %= mod
	return (size, ways)
t = int(input())
while t:
	t -= 1
	(n, m) = list(map(int, input().split()))
	ans = solve(1)
	print(ans[0], ans[1])


t = int(input())
for _ in range(t):
	(N, M) = map(int, input().split())
	total = 0
	numways = 1
	cont = True
	e = 0
	while cont:
		high = N // M ** e
		low = N // M ** (e + 1) + 1
		num = high - low + 1
		divs = num // M
		if low + divs * M <= high:
			r = (low + divs * M) % M
			if r == 0 or r + (high - (low + divs * M)) >= M:
				divs += 1
		nondivs = num - divs
		if e % 2 == 0:
			total += nondivs * ((e + 2) // 2)
		else:
			total += nondivs * (e // 2 + 1)
			numways = numways * pow((e + 3) // 2, nondivs, 998244353) % 998244353
		e += 1
		if low == 1:
			cont = False
	print(total, numways)


for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	(count, e, perm) = (0, 0, 1)
	while True:
		(lim, start) = (N // M ** e, N // M ** (e + 1) + 1)
		num = lim - start + 1
		divs = num // M
		if start + divs * M <= lim:
			r = (start + divs * M) % M
			if r == 0 or r + (lim - (start + divs * M)) >= M:
				divs += 1
		cmon = num - divs
		if e % 2 == 0:
			count += cmon * ((e + 2) // 2)
		else:
			count += cmon * (e // 2 + 1)
			perm = perm * pow((e + 3) // 2, cmon, 998244353) % 998244353
		e += 1
		if start == 1:
			break
	print(count, perm)


def power(x, y):
	p = 998244353
	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 func(a, b, m):
	no = a % m
	st = a
	if no != 0:
		st += m - no
	val = (b - st) // m + 1
	return b - a - val + 1
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	val = n
	ct = m
	flag = 1
	while ct <= n:
		val += (-1) ** flag * (n // ct)
		ct *= m
		flag ^= 1
	ot = 1
	ct = m
	p1 = 2
	while ct <= n:
		v = func(n // (ct * m) + 1, n // ct, m)
		ct *= m * m
		ot *= power(p1, v)
		p1 += 1
	print(val, ot % 998244353)