# 卢卡斯定理

def qmi(a,k):
    res  = 1
    while k:
        if k & 1:
            res = res * a % p
        a = a * a % p
        k >>= 1

    return res


def C(a,b,p):
    res = 1
    j = a
    for i in range(1,b+1):
        res = res * j % p
        res = res * qmi(i,p-2) % p
        j-=1

    return res


def lucas(a,b,p):
    if a < p and b < p: return C(a,b,p)
    return C(a % p, b % p,p) * lucas(a // p , b // p,p) % p

if __name__ == '__main__':
    for i in range(int(input())):
        a,b,p = map(int,input().split())
        print(lucas(a,b,p))