题解 | #快速乘#

n = int(input())
def cal(a, b, p):
    if b == 0:
        return 0
    while b != 0:
        if b % 2 == 0:
            b = b // 2
            c = cal(a, b, p)
            return (c + c) % p
        else:
            b = (b - 1) // 2
            c = cal(a, b, p)
            return (c + c + a % p) % p
for i in range(n):
    s = list(map(int, input().split()))
    a, b, p = s[0], s[1], s[2]
    print(cal(a, b, p))