#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;
}
思路