#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
int T;
int quick_power(int a,int k,int p)
{
    int res=1;
    while(k!=0)
    {
        if(k&1!=0) res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}
int c(int a,int b,int p)
{
    int res=1;
    for(int i=a;i>a-b;i--) res=(LL)res*i%p;
    for(int i=1;i<=b;i++) res=(LL)res*quick_power(i,p-2,p)%p;
    return res;
}
int lucas(LL a,LL b,int p)
{
    if(a<p&&b<p) return c(a,b,p);
    return (LL)c(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        LL a,b;int p;cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }
    return 0;
}