题解 | #快速幂#

import java.util.Scanner;

    public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//(a^b)%p = ((a%p)^b)%p
		Scanner scan = new Scanner(System.in);
		long q = scan.nextInt();
		while(q>0) {
			long a = scan.nextInt();
			long b = scan.nextInt();
			long p = scan.nextInt();
			
			long base = 1;
				while(b>0) {
					if(b%2!=0) {
                        //当b为奇数时
                        //a*(a*a)^(b/2);
						base = base*a;	
						base%=p;
					}
                    //当a为偶数时
                    //(a*a)^(b/2)
					a = a*a%p;
					b/=2;
				}	
				System.out.println(base%p);
				q--;
		}
}
}