#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
int n, p;

inline int qmi(int a, int k){
    LL res=1;
    while(k){
        if(k&0x01) res=res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    return res;
}

inline int C(int a, int b){
    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;
    }
    return res;
}

int lucas(LL a, LL b){
    if(a<p && b<p) return C(a, b);
    return (LL)C(a%p, b%p)*lucas(a/p, b/p)%p;
}

int main(){
    // lucas定理求解
    cin>>n;
    while(n--){
        LL a, b;
        cin>>a>>b>>p;
        cout<<lucas(a, b)<<endl;
    }
    return 0;
}