def quick_pow_mod_iterative(a, b, p):
    result = 1
    base = a % p
    while b > 0:
        if b % 2 == 1:  # b 是奇数
            result = (result * base) % p
        base = (base * base) % p
        b //= 2
    return result

n = int(input())
for _ in range(n):
    a, k, p = map(int, input().split())
    result = quick_pow_mod_iterative(a, k, p)
    print(result)