#include <iostream>
#define ZERO 0
using namespace std;

int queryNumber;

void declaration(){
    scanf("%d", &queryNumber);
}

long long downNumber, upNumber;
int model;

long long value;

long long quickPowerToInverse(long long numberToTransform){
    int exponentFromModel = model - 2;
    long long multiplyFactor = numberToTransform;
    long long multiplyAccumulation = 1;
    while (exponentFromModel != ZERO){
        if ((exponentFromModel & 1) != ZERO){
            multiplyAccumulation = multiplyAccumulation * multiplyFactor % model;
        }
        exponentFromModel >>= 1;
        multiplyFactor = multiplyFactor * multiplyFactor % model;
    }
    return multiplyAccumulation;
}

long long naiveCombination(long long upNumber, long long downNumber){
    long long combination = 1;
    long long iterateUpNumber = downNumber;
    long long iterateDownNumber = upNumber;
    for (int numberCounter = 1; numberCounter <= upNumber; numberCounter ++){
        combination = combination * iterateUpNumber % model;
        combination = combination * quickPowerToInverse(iterateDownNumber) % model;
        iterateUpNumber --;
        iterateDownNumber --;
    }
    return combination;
}

long long lucasMethod(long long upNumber, long long downNumber){
    if (upNumber < model && downNumber < model) return naiveCombination(upNumber, downNumber);
    else return naiveCombination(upNumber % model, downNumber % model) * lucasMethod(upNumber / model, downNumber / model) % model;
}

void outputValue(){
    printf("%lld\n", value);
}

void queries(){
    while (queryNumber --){
        scanf("%lld%lld%d", &downNumber, &upNumber, &model);
        value = lucasMethod(upNumber, downNumber);
        outputValue();
    }
}

int main(){
    declaration();
    queries();
    return 0;
}