#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const ll N=11;
ll T,n,m,k;
ll a[N+5][N+5],fac[N+5],pr[4]={2,3,5,7},mi[N+5][4];
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
inline void read(ll&x){
    x=0;char s=gc();
    while(!isdigit(s))s=gc();
    while(isdigit(s))x=x*10+(s^'0'),s=gc();
}
void print(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
namespace Solution{
	void init(){
		a[1][1]=1;
		for(ll i=2;i<=N;i++)
			for(ll j=1;j<=i;j++)
				a[i][j]=j*a[i-1][j]+a[i-1][j-1];
		fac[0]=1;
		for(ll i=1;i<=N;i++)fac[i]=fac[i-1]*i;
		for(ll i=1;i<=N;i++){
			ll t=i;
			for(ll j=0;j<4;j++){
				mi[i][j]=mi[i-1][j];
				while(t%pr[j]==0)mi[i][j]++,t/=pr[j];
			}
		}
		for(ll i=1;i<=N;i++)
			for(ll j=1;j<=i;j++)
				a[i][j]*=fac[j-1];
	}
	ll t[10],ans;
	ll C(ll n,ll k){
		ll ret=1;
		for(ll i=0;i<k;i++)t[i]=n-i;
		for(ll i=0;i<4;i++){
			ll cnt=mi[k][i];
			for(ll j=n-n/pr[i]*pr[i];j<k&&cnt;j+=pr[i]){
				while(cnt&&t[j]%pr[i]==0)t[j]/=pr[i],cnt--;
			}
		}
		for(ll i=0;i<k;i++)ret=ret*t[i]%m;
		return ret;
	}
	ll calc(ll n,ll k){
		ll ret=0;
		for(ll i=1;i<=k+1;i++)ret=(ret+C(n,i)*a[k+1][i]%m)%m;
		return ret;
	}
	void solve(){
		read(n),read(k),read(m);ans=0;
		for(ll l=1,r;l<=n;l=r+1){
			r=n/(n/l);
			ans=(ans+n/l*((calc(r,k)-calc(l-1,k)+m)%m)%m)%m;
		}
		print(ans),puts("");
	}
} 
int main(){
	Solution::init();
	for(read(T);T--;){
		Solution::solve();
	}
	return 0;
}

思路