题解 | #快速幂#

class Solution:

    def solve(self, a: int, b: int, p: int):
        result = 1

        smod = a % p
        runnum = b

        while runnum > 0:
            if runnum % 2 == 0:
                runnum = runnum >> 1
                smod = (smod * smod) % p
            else:
                runnum -= 1
                result = result * smod % p
        
        print(result)

    def calHalf(self, a: int):
        b = 0
        while a > (b + b):
            b += 1
        return b


if __name__ == '__main__':

    q = input() # 输入行信息
    q = int(q)
    solution = Solution()
    for _ in range(q):
        message = input()
        spinfo = message.split(" ")
        a = int(spinfo[0])
        b = int(spinfo[1])
        p = int(spinfo[2])
        solution.solve(a, b, p)