Read problems statements in mandarin chinese, russian and vietnamese as well. 

Chef has finally entered Guinness world records as a maker of longest sandwich in the world by breaking the previous record by making a sandwich of length N meters.

Celebrating this achievement, Chef decided to have a sandwich party with his friends, and of course no need to make more sandwiches, he will just cut his sandwich of length N meters into parts such that each part has positive integer length, and that too of at most K meters, otherwise it will be too long and it will be hard to be finished. 

Help Chef by telling him what's the minimum number of sandwiches (since he does not have many friends) the big sandwich has to be cut into, and in how many ways this can be done. Since the number of ways can be large output it modulo M

Two ways are said to be different if the positions of the cuts of first way is different from the positions of cuts of the second way.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follow.
Each line of the next T describes a test-case and contains three integers N, K and M.

------ Output ------ 

For each test case, output a single line containing two space separated integers, minimum number of sandwiches and number of ways to cut the large sandwich into minimum number of sandwiches modulo M.

------ Constraints ------ 

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 10^{18}$
$1 ≤ K ≤ 10^{18}$
$2 ≤ M ≤ 10^{6}$

------ Subtasks ------ 

$Subtask #1 (10 points) 1 ≤ N, K ≤ 50 $
$Subtask #2 (20 points) 1 ≤ N, K ≤ 1,000,000$
$Subtask #3 (20 points) M is prime$
$Subtask #4 (50 points) original constraints$

----- Sample Input 1 ------ 
2

7 3 500

10 2 1000
----- Sample Output 1 ------ 
3 6

5 1
----- explanation 1 ------ 
Example case 1. The minimum number of sandwiches is 3, and there are 6 ways to make 2 cuts:

positions: 1 4
positions: 3 4
positions: 3 6
positions: 2 4
positions: 2 5
positions: 3 5

Example case 2. The minimum number of sandwiches is 5, and the only way is to make all the 5 sandwiches have length 2

Difficulty: VERY_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
from collections import Counter, deque, defaultdict
from functools import lru_cache, reduce
from heapq import heappush, heappop, heapify, heappushpop, _heappop_max, _heapify_max

def _heappush_max(heap, item):
	heap.append(item)
	heapq._siftdown_max(heap, 0, len(heap) - 1)

def _heappushpop_max(heap, item):
	if heap and item < heap[0]:
		(item, heap[0]) = (heap[0], item)
		heapq._siftup_max(heap, 0)
	return item
from math import gcd as GCD
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def LCM(n, m):
	if n or m:
		return abs(n) * abs(m) // math.gcd(n, m)
	return 0

def Extended_Euclid(n, m):
	stack = []
	while m:
		stack.append((n, m))
		(n, m) = (m, n % m)
	if n >= 0:
		(x, y) = (1, 0)
	else:
		(x, y) = (-1, 0)
	for i in range(len(stack) - 1, -1, -1):
		(n, m) = stack[i]
		(x, y) = (y, x - n // m * y)
	return (x, y)

class MOD:

	def __init__(self, mod):
		self.mod = mod

	def Pow(self, a, n):
		a %= self.mod
		if n >= 0:
			return pow(a, n, self.mod)
		else:
			assert math.gcd(a, self.mod) == 1
			x = Extended_Euclid(a, self.mod)[0]
			return pow(x, -n, self.mod)

	def Build_Fact(self, N):
		assert N >= 0
		self.factorial = [1]
		for i in range(1, N + 1):
			self.factorial.append(self.factorial[-1] * i % self.mod)
		self.factorial_inv = [None] * (N + 1)
		self.factorial_inv[-1] = self.Pow(self.factorial[-1], -1)
		for i in range(N - 1, -1, -1):
			self.factorial_inv[i] = self.factorial_inv[i + 1] * (i + 1) % self.mod
		return self.factorial_inv

	def Fact(self, N):
		return self.factorial[N]

	def Fact_Inv(self, N):
		return self.factorial_inv[N]

	def Comb(self, N, K):
		if K < 0 or K > N:
			return 0
		s = self.factorial[N]
		s = s * self.factorial_inv[K] % self.mod
		s = s * self.factorial_inv[N - K] % self.mod
		return s

class Prime:

	def __init__(self, N):
		self.smallest_prime_factor = [None] * (N + 1)
		for i in range(2, N + 1, 2):
			self.smallest_prime_factor[i] = 2
		n = int(N ** 0.5) + 1
		for p in range(3, n, 2):
			if self.smallest_prime_factor[p] == None:
				self.smallest_prime_factor[p] = p
				for i in range(p ** 2, N + 1, 2 * p):
					if self.smallest_prime_factor[i] == None:
						self.smallest_prime_factor[i] = p
		for p in range(n, N + 1):
			if self.smallest_prime_factor[p] == None:
				self.smallest_prime_factor[p] = p
		self.primes = [p for p in range(N + 1) if p == self.smallest_prime_factor[p]]

	def Factorize(self, N):
		assert N >= 1
		factorize = defaultdict(int)
		if N <= len(self.smallest_prime_factor) - 1:
			while N != 1:
				factorize[self.smallest_prime_factor[N]] += 1
				N //= self.smallest_prime_factor[N]
		else:
			for p in self.primes:
				while N % p == 0:
					N //= p
					factorize[p] += 1
				if N < p * p:
					if N != 1:
						factorize[N] += 1
					break
				if N <= len(self.smallest_prime_factor) - 1:
					while N != 1:
						factorize[self.smallest_prime_factor[N]] += 1
						N //= self.smallest_prime_factor[N]
					break
			else:
				if N != 1:
					factorize[N] += 1
		return factorize

	def Divisors(self, N):
		assert N > 0
		divisors = [1]
		for (p, e) in self.Factorize(N).items():
			A = [1]
			for _ in range(e):
				A.append(A[-1] * p)
			divisors = [i * j for i in divisors for j in A]
		return divisors

	def Is_Prime(self, N):
		return N == self.smallest_prime_factor[N]

	def Totient(self, N):
		for p in self.Factorize(N).keys():
			N *= p - 1
			N //= p
		return N

class Lucas_Prime:

	def __init__(self, P, e=1, divisible_count=False):
		self.P = P
		self.e = e
		self.divisible_count = divisible_count
		self.mod = self.P ** self.e
		self.factorial = [1]
		for i in range(1, self.mod):
			self.factorial.append(self.factorial[-1])
			if i % P:
				self.factorial[i] *= i
				self.factorial[i] %= self.mod

	def Comb(self, N, K):
		if K < 0 or K > N:
			return 0
		(K0, K1) = (K, N - K)
		N_lst = []
		N_ = N
		while N_:
			N_lst.append(N_ % self.mod)
			N_ //= self.P
		K0_lst = []
		K0_ = K0
		for _ in range(len(N_lst)):
			K0_lst.append(K0_ % self.mod)
			K0_ //= self.P
		K1_lst = []
		K1_ = K1
		for _ in range(len(N_lst)):
			K1_lst.append(K1_ % self.mod)
			K1_ //= self.P
		(retu, retu_rev) = (1, 1)
		for n in N_lst:
			retu *= self.factorial[n]
			retu %= self.mod
		for k0 in K0_lst:
			retu_rev *= self.factorial[k0]
			retu_rev %= self.mod
		for k1 in K1_lst:
			retu_rev *= self.factorial[k1]
			retu_rev %= self.mod
		retu *= MOD(self.mod).Pow(retu_rev, -1)
		if self.P != 2 or self.e <= 2:
			cnt = 0
			N_ = N // self.mod
			K0_ = K0 // self.mod
			K1_ = K1 // self.mod
			while N_:
				cnt += N_
				N_ //= self.P
			while K0_:
				cnt += K0_
				K0_ //= self.P
			while K1_:
				cnt += K1_
				K1_ //= self.P
			if cnt % 2 == 1:
				retu *= -1
		retu %= self.mod
		div_cnt = 0
		(N_, K0_, K1_) = (N, K0, K1)
		while N_:
			div_cnt += N_
			N_ //= self.P
		while K0_:
			div_cnt -= K0_
			K0_ //= self.P
		while K1_:
			div_cnt -= K1_
			K1_ //= self.P
		if self.divisible_count:
			return (retu, div_cnt)
		else:
			retu *= pow(self.P, div_cnt, self.mod)
			retu %= self.mod
			return retu

class Lucas:

	def __init__(self, mod):
		self.mod = mod
		P = Prime(int(self.mod ** 0.5))
		self.factorize = P.Factorize(mod)
		self.L = {p: Lucas_Prime(p, e) for (p, e) in self.factorize.items()}

	def Comb(self, N, K):
		lst_r = []
		lst_m = []
		for (p, e) in self.factorize.items():
			lst_r.append(self.L[p].Comb(N, K))
			lst_m.append(p ** e)
		(r, _) = CRT(lst_r, lst_m)
		return r

def CRT(lst_r, lst_m):
	(r, m) = (lst_r[0], lst_m[0])
	for (r0, m0) in zip(lst_r[1:], lst_m[1:]):
		if (r0, m0) == (-1, 0):
			(r, m) = (-1, 0)
			break
		r0 %= m0
		g = math.gcd(m, m0)
		l = LCM(m, m0)
		if r % g != r0 % g:
			(r, m) = (-1, 0)
			break
		(r, m) = ((r0 + m0 * ((r - r0) // g * Extended_Euclid(m0 // g, m // g)[0] % (m // g))) % l, l)
	return (r, m)
T = int(readline())
for _ in range(T):
	(N, K, M) = map(int, readline().split())
	ans0 = (N + K - 1) // K
	ans1 = Lucas(M).Comb(ans0 * K - N + ans0 - 1, ans0 - 1)
	print(ans0, ans1)


globalFacts = dict()

def compute(n, m, big):
	y = decompose(big)
	remainders = []
	for powerPrime in y:
		remainders.append(binomialModulo(n, m, powerPrime[0], powerPrime[1]))
	sol = chaineseRemainderTheorem([pow(i[0], i[1]) for i in y], remainders)
	return sol

def chaineseRemainderTheorem(num, rem):
	prod = 1
	for i in num:
		prod *= i
	resultch = 0
	for i in range(len(num)):
		pp = prod // num[i]
		resultch += rem[i] * inverse(pp, num[i]) * pp
	return resultch % prod

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

def inverse(a, m):
	(g, x, y) = egcd(a, m)
	return x % m

def binomialModulo(n, m, prime, powerPrime):
	power = int(pow(prime, powerPrime))
	(nArray, mArray, rArray, NArray, MArray, RArray, e0, eq) = allAtOnce(n, m, prime, powerPrime)
	resultb = 1
	denominator = 1
	resultb = pow(-1, eq) * pow(prime, e0) % power
	if resultb == 0:
		return 0
	for i in range(len(nArray)):
		resultb *= fact(NArray[i], prime, powerPrime)
		denominator *= fact(MArray[i], prime, powerPrime) * fact(RArray[i], prime, powerPrime)
		resultb = resultb % power
		denominator = denominator % power
	resultb *= inverse(denominator % power, power)
	return resultb % power

def fact(k, prime, powerPrime):
	power = pow(prime, powerPrime)
	if (k, power) in globalFacts:
		return globalFacts[k, power]
	factorial = 1
	for i in range(1, k + 1):
		if i % prime != 0:
			factorial = factorial * i % power
	globalFacts[k, power] = factorial
	return factorial

def allAtOnce(n, m, prime, powerPrime):
	nArray = []
	mArray = []
	rArray = []
	NArray = []
	MArray = []
	RArray = []
	r = n - m
	e0 = 0
	eq = 0
	j = 0
	power = int(pow(prime, powerPrime))
	while n > 0:
		nArray.append(n % prime)
		mArray.append(m % prime)
		rArray.append(r % prime)
		NArray.append(n % power)
		MArray.append(m % power)
		RArray.append(r % power)
		n = n // prime
		r = r // prime
		m = m // prime
		j = j + 1
		if n != m + r:
			e0 = e0 + 1
			if j >= powerPrime:
				eq = eq + 1
	return (nArray, mArray, rArray, NArray, MArray, RArray, e0, eq)

def decompose(big):
	elements = []
	counter = 2
	numele = 0
	while big > 1:
		if big % counter == 0:
			exponente = 0
			while big % counter == 0:
				big = big // counter
				exponente = exponente + 1
			elements.append([])
			elements[numele].append(counter)
			elements[numele].append(exponente)
			numele = numele + 1
		counter += 1
	return elements
t = int(input().strip())
for ii in range(t):
	cadena = input()
	arr = [int(s) for s in cadena.split()]
	nn = arr[0]
	kk = arr[1]
	mm = arr[2]
	c = (nn + kk - 1) // kk
	L = c * kk - nn + c - 1
	result = compute(L, c - 1, mm)
	print(c, result)


import math
from functools import reduce
from collections import Counter
import math
from functools import reduce
from collections import Counter

def det(n, p):
	(ret, n) = (0, n // p)
	while n:
		(ret, n) = (ret + n, n // p)
	return ret

def binomial(a, b, X):
	pri = X[0]
	ex = X[1]
	rem = pri ** ex
	expp = det(a, pri) - det(b, pri) - det(a - b, pri)
	inverse = rem - rem // pri - 1
	if expp >= ex:
		return 0
	else:
		ttteeemmmppp = 1
		for i in range(1, rem + 1):
			if i % pri != 0:
				ttteeemmmppp *= i
				ttteeemmmppp %= rem
				rfact[i] = ttteeemmmppp
			else:
				rfact[i] = ttteeemmmppp

		def f(t):
			if t == 0:
				return 1
			teem = pow(rfact[rem], t // rem, rem)
			ans = 0
			if t % rem == 0:
				ans = teem
			else:
				ans = teem * rfact[t % rem]
				ans %= rem
			return ans

		def F(t):
			eeee = t
			count = 0
			while eeee // pri > 0:
				eeee = eeee // pri
				count += 1
			temm = 1
			for i in range(0, count + 1):
				temm *= f(t // pri ** i)
				temm %= rem
			return temm
		Ans = pow(pri, expp) * F(a)
		Ans %= rem
		temp22 = F(b) * F(a - b) % rem
		temp22 = pow(temp22, inverse, rem)
		Ans = Ans * temp22
		Ans %= rem
		return Ans
Test = int(input())
total = []
MAX = 0
for _ in range(Test):
	(N, K, M) = list(map(int, input().strip().split(' ')))
	total += [[N, K, M]]
	if M > MAX:
		MAX = M
prime = [-1 for i in range(MAX + 1)]
for i in range(2, MAX + 1):
	if prime[i] == -1:
		temp = MAX // i
		for j in range(2, temp + 1):
			prime[j * i] = 1
primeset = []
for i in range(2, MAX + 1):
	if prime[i] == -1:
		primeset += [i]

def Chinese(n, a):
	s = 0
	prod = reduce(lambda a, b: a * b, n)
	for (n_i, a_i) in zip(n, a):
		p = prod // n_i
		s += a_i * mul(p, n_i) * p
	return s % prod

def factor(A):
	if A == 1:
		return []
	else:
		Temp = []
		check = 0
		while 1:
			if A == 1:
				break
			i = check
			while i < len(primeset):
				if A % primeset[i] == 0:
					check = i
					A = A // primeset[i]
					Temp += [primeset[i]]
					i += 1
					break
				else:
					i += 1
		AB = Counter(Temp)
		D = []
		for x in AB:
			D += [[x, AB[x]]]
		return D

def mul(c, d):
	b0 = d
	(x0, x1) = (0, 1)
	if d == 1:
		return 1
	while c > 1:
		q = c // d
		(c, d) = (d, c % d)
		(x0, x1) = (x1 - q * x0, x0)
	if x1 < 0:
		x1 += b0
	return x1
for i in range(len(total)):
	(N, K, M) = total[i]
	factors = factor(M)
	Chin = []
	for ii in range(len(factors)):
		Chin += [factors[ii][0] ** factors[ii][1]]
	if N % K == 0:
		print(N // K, 1)
	else:
		r = N // K + 1
		T = K - N % K
		upp = r + T - 1
		data = []
		for i in range(len(factors)):
			(A, B) = factors[i]
			CC = A ** B
			rfact = [1] * (CC + 1)
			data += [binomial(upp, T, [A, B])]
		if len(factors) == 1:
			China = data[0]
		else:
			China = Chinese(Chin, data)
		print(r, China)


from functools import *
import math
import operator

def len_in_bits(n):
	try:
		return n.bit_length()
	except AttributeError:
		if n == 0:
			return 0
		return len(bin(n)) - 2

def randint_bits(size):
	low = 1 << size - 1
	hi = (1 << size) - 1
	return random.randint(low, hi)

def ceil(x, y):
	return x / y + (x % y != 0)

def nroot(x, n):
	if n < 0:
		raise ValueError("can't extract negative root")
	if n == 0:
		raise ValueError("can't extract zero root")
	sign = 1
	if x < 0:
		sign = -1
		x = -x
		if n % 2 == 0:
			raise ValueError("can't extract even root of negative")
	high = 1
	while high ** n <= x:
		high <<= 1
	low = high >> 1
	while low < high:
		mid = low + high >> 1
		if low < mid and mid ** n < x:
			low = mid
		elif high > mid and mid ** n > x:
			high = mid
		else:
			return sign * mid
	return sign * (mid + 1)

def _gcd(a, b):
	if a == 0:
		return b
	if b == 0:
		return a
	while b:
		(a, b) = (b, a % b)
	return abs(a)

def _lcm(a, b):
	if not a or not b:
		raise ZeroDivisionError('lcm arguments may not be zeros')
	return abs(a * b) // _gcd(a, b)

def gcd(*lst):
	return abs(reduce(lambda a, b: _gcd(a, b), lst))

def lcm(*lst):
	return reduce(lambda a, b: _lcm(a, b), lst)

def xgcd(a, b):
	if a == 0:
		return (0, 1, b)
	if b == 0:
		return (1, 0, a)
	(px, ppx) = (0, 1)
	(py, ppy) = (1, 0)
	while b:
		q = a // b
		(a, b) = (b, a % b)
		x = ppx - q * px
		y = ppy - q * py
		(ppx, px) = (px, x)
		(ppy, py) = (py, y)
	return (ppx, ppy, a)

def extract_prime_power(a, p):
	s = 0
	if p > 2:
		while a and a % p == 0:
			s += 1
			a //= p
	elif p == 2:
		while a and a & 1 == 0:
			s += 1
			a >>= 1
	else:
		raise ValueError('Number %d is not a prime (is smaller than 2)' % p)
	return (s, a)

def solve_linear(a, b, c):
	return None

def grey_code(n):
	return n ^ n >> 1

def rev_grey_code(g):
	n = 0
	while g:
		n ^= g
		g >>= 1
	return n

def factorial(n):
	res = 1
	while n > 1:
		res *= n
		n -= 1
	return res

def factorial_get_prime_pow(n, p):
	count = 0
	ppow = p
	while ppow <= n:
		count += n // ppow
		ppow *= p
	return count

def nCk(n, k):
	if n < 0:
		raise ValueError('Invalid value for n: %s' % n)
	if k < 0 or k > n:
		return 0
	if k in (0, n):
		return 1
	if k in (1, n - 1):
		return n
	low_min = 1
	low_max = min(n, k)
	high_min = max(1, n - k + 1)
	high_max = n
	return reduce(operator.mul, range(high_min, high_max + 1), 1) / reduce(operator.mul, range(low_min, low_max + 1), 1)

def has_invmod(a, modulus):
	if modulus < 2:
		raise ValueError('modulus must be greater than 1')
	if a == 0 or gcd(a, modulus) != 1:
		return False
	else:
		return True

def invmod(a, n):
	if n < 2:
		raise ValueError('modulus must be greater than 1')
	(x, y, g) = xgcd(a, n)
	if g != 1:
		raise ValueError('no invmod for given @a and @n')
	else:
		return x % n

def solve_crt(remainders, modules):
	if len(modules) != len(remainders):
		raise TypeError('modules and remainders lists must have same len')
	if len(modules) == 0:
		raise ValueError('Empty lists are given')
	if len(modules) == 1:
		return remainders[0]
	x = 0
	N = reduce(operator.mul, modules)
	for (i, module) in enumerate(modules):
		if module == 1:
			continue
		Ni = N // module
		b = invmod(Ni, module)
		x += remainders[i] * Ni * b
	return x % N

def nCk_mod(n, k, factors):
	rems = []
	mods = []
	for (p, e) in factors.items():
		rems.append(nCk_mod_prime_power(n, k, p, e))
		mods.append(p ** e)
	return solve_crt(rems, mods)

def factorial_mod(n, factors):
	rems = []
	mods = []
	for (p, e) in factors.items():
		pe = p ** e
		if n >= pe or factorial_get_prime_pow(n, p) >= e:
			factmod = 0
		else:
			factmod = factorial(n) % pe
		rems.append(factmod)
		mods.append(pe)
	return solve_crt(rems, mods)

def nCk_mod_prime_power(n, k, p, e):

	def nCk_get_prime_pow(n, k, p):
		res = factorial_get_prime_pow(n, p)
		res -= factorial_get_prime_pow(k, p)
		res -= factorial_get_prime_pow(n - k, p)
		return res

	def nCk_get_non_prime_part(n, k, p, e):
		pe = p ** e
		r = n - k
		fact_pe = [1]
		acc = 1
		for x in range(1, pe):
			if x % p == 0:
				x = 1
			acc = acc * x % pe
			fact_pe.append(acc)
		top = bottom = 1
		is_negative = 0
		digits = 0
		while n != 0:
			if acc != 1:
				if digits >= e:
					is_negative ^= n & 1
					is_negative ^= r & 1
					is_negative ^= k & 1
			top = top * fact_pe[n % pe] % pe
			bottom = bottom * fact_pe[r % pe] % pe
			bottom = bottom * fact_pe[k % pe] % pe
			n //= p
			r //= p
			k //= p
			digits += 1
		res = top * invmod(bottom, pe) % pe
		if p != 2 or e < 3:
			if is_negative:
				res = pe - res
		return res
	prime_part_pow = nCk_get_prime_pow(n, k, p)
	if prime_part_pow >= e:
		return 0
	modpow = e - prime_part_pow
	r = nCk_get_non_prime_part(n, k, p, modpow) % p ** modpow
	return p ** prime_part_pow * r % p ** e
sieve = [0 for x in range(1000010)]
for i in range(2, 1000001):
	if sieve[i] == 0:
		sieve[i] = i
		for j in range(i * i, 1000001, i):
			sieve[j] = i
primes = [x for x in range(2, 1000001) if sieve[x] == 1]
t = int(input())
for i in range(t):
	(n, k, m) = list(map(int, input().split()))
	tmpm = int(m)
	facs = {}
	while tmpm > 1:
		x = sieve[tmpm]
		c = 0
		while tmpm % x == 0:
			c += 1
			tmpm //= x
		facs[x] = c
	p = n // k
	rem = n % k
	tmp = p
	ans = 1
	if rem == 0:
		ans = 1
	else:
		ans = (ans + nCk_mod(p + (k - rem) % k, p, facs) - 1) % m
	print(p + int(rem > 0), ans)


import sys

def factorise(m):
	ans = []
	p = 2
	while m != 1:
		if m % p != 0:
			p += 1
			continue
		e = 0
		while m % p == 0:
			m //= p
			e += 1
		ans.append([p, e])
		p += 1
	return ans

def mulmod(a, b, c):
	res = a * b
	if res >= c:
		res %= c
	return res

def mod_inverse(a, n):
	N = n
	xx = 0
	yy = 1
	y = 0
	x = 1
	while n > 0:
		q = a // n
		t = n
		n = a % n
		a = t
		t = xx
		xx = x - q * xx
		x = t
		t = yy
		yy = y - q * yy
		y = t
	x %= N
	x += N
	x %= N
	return x

def expo(a, b):
	x = 1
	y = a
	while b > 0:
		if b & 1:
			x = x * y
		y = y * y
		b >>= 1
	return x

def power(a, b, c):
	x = 1
	y = a
	while b > 0:
		if b & 1:
			x = mulmod(x, y, c)
		y = mulmod(y, y, c)
		b >>= 1
	return x

def init(p, pk):
	fact = []
	fact.append(1)
	for i in range(1, pk):
		red = i
		if red % p == 0:
			red = 1
		fact.append(mulmod(fact[i - 1], red, pk))
	return fact

def fact_mod(n, p, pk, fact):
	res = 1
	while n > 0:
		times = n // pk
		res = mulmod(res, power(fact[pk - 1], times, pk), pk)
		res = mulmod(res, fact[n % pk], pk)
		n //= p
	return res

def count_fact(n, p):
	ans = 0
	while n > 0:
		ans += n // p
		n //= p
	return ans

def ncr(n, r, p, e):
	if r > n or r < 0:
		return 0
	if r == 0 or n == r:
		return 1
	_e = count_fact(n, p) - count_fact(r, p) - count_fact(n - r, p)
	assert _e >= 0
	if _e >= e:
		return 0
	pk = expo(p, e)
	fact = init(p, pk)
	ans = fact_mod(n, p, pk, fact)
	ans = mulmod(ans, mod_inverse(fact_mod(r, p, pk, fact), pk), pk)
	ans = mulmod(ans, mod_inverse(fact_mod(n - r, p, pk, fact), pk), pk)
	ans = mulmod(ans, expo(p, _e), pk)
	return ans

def pre_process(rem, mods):
	crt = []
	a = 1
	b = 1
	m = mods[0]
	crt.append([mods[0], a, b])
	L = len(mods)
	for i in range(1, L):
		a = mod_inverse(m, mods[i])
		b = mod_inverse(mods[i], m)
		crt.append([m, a, b])
		m *= mods[i]
	assert len(crt) == len(mods)
	return crt

def find_crt(crt):
	assert len(crt) == len(mods)
	ans = rem[0]
	m = crt[0][0]
	L = len(mods)
	for i in range(1, L):
		a = crt[i][1]
		b = crt[i][2]
		m = crt[i][0]
		_m = m * mods[i]
		ans = mulmod(ans, b * mods[i], _m)
		ans = (ans + mulmod(rem[i], a * m, _m)) % _m
	return ans
inpos = sys.stdin
t = int(inpos.readline())
for _ in range(t):
	[n, k, m] = list(map(int, inpos.readline().split()))
	ans = (n + k - 1) // k
	ans2 = 1
	if n % k != 0:
		pf = factorise(m)
		rem = []
		mods = []
		b = k - n % k
		a = n // k + b
		L = len(pf)
		for i in range(L):
			get = ncr(a, b, pf[i][0], pf[i][1])
			rem.append(get)
			mods.append(expo(pf[i][0], pf[i][1]))
		crt = pre_process(rem, mods)
		ans2 = find_crt(crt)
	ans2 %= m
	assert 0 <= ans2 and ans2 < m
	print(ans, ans2)


LIM = 10 ** 6 + 5

def sieve():
	global primes, is_prime
	is_prime = [True] * LIM
	is_prime[0] = is_prime[1] = False
	i = 2
	while i * i <= LIM:
		if is_prime[i]:
			for j in range(i * i, LIM, i):
				is_prime[j] = False
		i += 1
	primes = [i for i in range(LIM) if is_prime[i]]
sieve()

def mod_inverse(n, m):
	t = 0
	newt = 1
	r = m
	newr = n
	while newr:
		q = r // newr
		(t, newt) = (newt, t - q * newt)
		(r, newr) = (newr, r - q * newr)
	if r > 1:
		return None
	if t < 0:
		t += m
	return t

def prime_factorize(n):
	fac = []
	for p in primes:
		if p * p > n:
			break
		q = 0
		while n % p == 0:
			q += 1
			n //= p
		if q > 0:
			fac.append((p, q))
	if n > 1:
		fac.append((n, 1))
	return fac

def chinese_rt(divs, rems):
	prod = 1
	for d in divs:
		prod *= d
	res = 0
	for i in range(len(divs)):
		d_rmvd_prod = prod // divs[i]
		res += rems[i] * d_rmvd_prod * mod_inverse(d_rmvd_prod, divs[i])
		res %= prod
	return res

def n_choose_k_mod_p_pow_q(n, k, p, q):
	pq = p ** q
	p_rmvd_fact = [1]
	for i in range(1, pq):
		p_rmvd_fact.append(p_rmvd_fact[-1])
		if i % p > 0:
			p_rmvd_fact[-1] *= i
			p_rmvd_fact[-1] %= pq
	r = n - k
	num = den = 1
	e0 = eq = dig = 0
	sum_ = carry = 0
	while n:
		num *= p_rmvd_fact[n % pq]
		den *= p_rmvd_fact[k % pq] * p_rmvd_fact[r % pq]
		num %= pq
		den %= pq
		sum_ = k % p + r % p + carry
		carry = sum_ // p
		if carry > 0:
			e0 += 1
			if dig >= q:
				eq += 1
		n //= p
		k //= p
		r //= p
		dig += 1
	res = p ** e0 * num * mod_inverse(den, pq) % pq
	if p != 2 or q < 3:
		if eq % 2 == 1:
			res = pq - res
	return res

def n_choose_k_mod_m(n, k, m):
	m_fac = prime_factorize(m)
	(divs, rems) = ([], [])
	for (p, q) in m_fac:
		r = n_choose_k_mod_p_pow_q(n, k, p, q)
		divs.append(p ** q)
		rems.append(r)
	res = chinese_rt(divs, rems)
	return res
for t in range(int(input())):
	(N, K, M) = map(int, input().split())
	K = min(K, N)
	pieces = N // K + (1 if N % K else 0)
	extra = pieces * K - N
	n = extra + pieces - 1
	k = pieces - 1
	ans = n_choose_k_mod_m(n, k, M)
	print(pieces, ans)


from collections import defaultdict
PMAX = 10 ** 5
bprimes = [True] * PMAX
primes = []
for i in range(2, 1000):
	if bprimes[i]:
		t = i * i
		while t < PMAX:
			bprimes[t] = False
			t += i
for i in range(2, PMAX):
	if bprimes[i]:
		primes.append(i)

def factor_small(n):
	fdict = defaultdict(int)
	for p in primes:
		if n <= 1:
			break
		if p * p > n:
			fdict[n] += 1
			break
		while n % p == 0:
			fdict[p] += 1
			n //= p
	return fdict

def inv(n, m):
	(nn, nm, mn, mm) = (1, 0, 0, 1)
	while m:
		(div, mod) = divmod(n, m)
		nn -= mn * div
		nm -= mm * div
		n = mod
		(n, m) = (m, n)
		(nn, nm, mn, mm) = (mn, mm, nn, nm)
	return nn

def co_mod(mod_remains):
	prod_all = 1
	for mod in mod_remains:
		prod_all *= mod
	res = 0
	for (mod, remain) in mod_remains.items():
		prod_others = prod_all // mod
		res += remain * prod_others * inv(prod_others, mod)
		res %= prod_all
	res = (res + prod_all) % prod_all
	return res

def comb_ppm(n, m, prime, power):
	ppm = prime ** power
	facts = [1, 1]
	for f in range(2, ppm):
		if f % prime == 0:
			facts.append(facts[-1])
		else:
			facts.append(facts[-1] * f % ppm)
	r = n - m
	pos = 0
	carry = 0
	carryq1 = 0
	(tn, tm, tr) = (n, m, r)
	while tn > 0 or tm > 0:
		nm = tn % prime
		mm = tm % prime
		rm = tr % prime
		if nm < mm or nm < rm:
			carry += 1
			if pos >= power - 1:
				carryq1 += 1
		tn //= prime
		tm //= prime
		tr //= prime
		pos += 1
	res = 1
	(tn, tm, tr) = (n, m, r)
	while tn > 0 or tm > 0 or tr > 0:
		nm = tn % ppm
		mm = tm % ppm
		rm = tr % ppm
		res *= facts[nm]
		res *= inv(facts[mm], ppm)
		res *= inv(facts[rm], ppm)
		res %= ppm
		res = (res + ppm) % ppm
		tn //= prime
		tm //= prime
		tr //= prime
	res *= prime ** carry
	res %= ppm
	if carryq1 % 2 == 1 and (prime != 2 or power < 3):
		res = (ppm - res) % ppm
	return res

def comb(n, r, m):
	comb_by_ppms = {}
	for (prime, count) in factor_small(m).items():
		comb_by_ppms[prime ** count] = comb_ppm(n, r, prime, count)
	return co_mod(comb_by_ppms)
T = int(input())
for _ in range(T):
	(N, K, M) = map(int, input().split())
	scount = (N + K - 1) // K
	if N % K == 0:
		kind = 1
	else:
		kind = comb(N // K + K - N % K, N // K, M)
	print(scount, kind)