#时间复杂度是 log（k)

def qmi(a,k,p):
    res = 1
    while k:
        if k & 1:               #如果当前k末尾是1
            res = res * a % p   #那么乘以上一次运算a的平方 (a^k%p)
        k >>= 1                 #每次算完，删掉末尾k（二进制）
        a = a * a % p           #每次把a平方 (a^k%p)

    return res

if __name__ =='__main__':
    n = int(input())

    for i in range(n):
        a, k, p = map(int,input().split())
        print(a, k, p)
        print(qmi(a, k, p))