技巧
    快速幂
思路
    数学性质  如    7^10  =  7^5 * 7^5
                            7^5    =   7^2  * 7^2 * 7^1
    这里要注意  两个大数字直接相乘然后取模可能会爆掉  需要把乘法转换成加法一次一次的运算取模
    相乘的话 例如 3 * 5 （011 * 101） 代表3个5 相加。  101可以看成 1个3 和4个3相加   循环时候a保持倍增即可
   
实现 
package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
)
// 乘法转加法每次都mod 防止a*b爆掉
func mul(a, b ,mod int) int{
    ans := 0
    for b != 0 {
        if b & 1 == 1 {
            ans = (ans + a) % mod
        }
        a = (a + a) % mod
        b >>= 1
    }
    return ans
}

// 快速幂模板 - 循环
func qpow(A, B, P int) int{
    ans := 1
    for B != 0 {
        if (B & 1) != 0 {
            ans = mul(ans, A, P)
        }
        A  =  mul(A, A, P)
        B >>=1
    }
    return ans
}

// 快速幂模板 - 递归
func qpow1(A, B, P int) int{
    if B == 0 {
        return 1
    }
    if B % 2 == 1 {
        return mul(qpow1(A, B-1, P), A, P)
    }else {
        tmp := qpow1(A, B/2,P)
        return mul(tmp, tmp, P)
    }
}

// https://ac.nowcoder.com/acm/problem/23046
func NC23046(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
    var T int
    for Fscan(in, &T); T > 0; T-- {
        var A, B, P int
        Fscan(in, &A, &B, &P)
        Fprintln(out, qpow1(A,B,P))
    }
}

func main() {
	NC23046(os.Stdin, os.Stdout)
}