这题数据范围比较大（$10^{18}$倒不至于，纯吓唬人），可以用卢卡斯定理求结果

卢卡斯定理： $C_a^b = C_{a\%p}^{b\%p}\ * C_{a/p}^{b/p}$，$p$ 是取模的质数。详情见代码注释

#include <bits/stdc++.h>
typedef long long ll;
int p;
int qmi(int a, int k) // p是全局变量，就不作形参了。快速幂求逆元模板，用于对需要取模的数的除法。
{
	int res = 1;
	while (k)
	{
		if (k & 1) res = (ll) res * a % p;
		a = (ll)a * a % p;
		k >>= 1;
	}
	return res;
}
int C(int a, int b)// a和b比较小的时候，用C函数直接求结果
{
	int res = 1;
	for (int i = 1, j = a; i <= b; i ++, j -- )
	{
		res = (ll)res * j % p;
		res = (ll)res * qmi(i, p-2) % p;//qmi(i,mod-2) 是i模p的逆元，即1/i (% p)。此处用的是组合数的定义式求解
	}
	return res;
}
ll lucas(ll a, ll b)// a和b很大的时候用lucas函数
{
	if (a < p && b < p) return C(a, b) % p;// 如果a,b小于p，数据已经变小，可以直接求结果
	return (ll)C(a % p, b % p) * lucas(a / p, b / p) % p;// 数据很大，使用lucas定理递归
}
int main()
{
	int t;
	std::cin >> t;
	while (t --)
	{
		ll a, b;
		std::cin >> a >> b >> p;
		std::cout << lucas(a, b) << std::endl;
	}
	return 0;
}