package main
import "fmt"
import "bufio"
import "os"

var reader=bufio.NewReader(os.Stdin)
var writer=bufio.NewWriter(os.Stdout)

// 快速幂 快速平方发, 求 (a^b)%p
// b= b0*2^p0 + b1*2^p1 + b2*2^p2 ... + bn*2^pn , 其中p0~pn是二进制位数，b0~bn是二进制对应位置是0还是1.
// a^b = a^(b0*2^p0) * a^(b1*2^p1) ... * a^(bn*2^pn)
// 如果 bi=0, 则 a^(bi*2^pi) = 1, 不用计算
// 
func fastPower(a,b,p uint64) uint64{
    a%=p
    var res uint64 = 1
    for b>0{
        // 该位二进制不为0
        if b&1 > 0{
            res = (res*a)%p
        }

        // a = a^2
        a=(a*a)%p

        b>>=1
    }
    return res
}

func main(){
    var n int
    fmt.Fscan(reader, &n)
    var a,b,p uint64
    for i:=0;i<n;i++{
        fmt.Fscan(reader, &a,&b,&p)
        fmt.Fprintln(writer, fastPower(a,b,p))
    }
    writer.Flush()
}