题解 | #快速幂#

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        long a;
        long b;
        long p;
        for(int i = 0; i < n; i++){
            a = input.nextInt();
            b = input.nextInt();
            p = input.nextInt();
            System.out.println(cal(a,b,p));
        }
    }       
    public static long cal(long a, long b, long p){
        //根据公式 (a1*a2)^b %p = (a1%p)^b * (a2%p)^b %p可以进行快速幂计算
        long res = 1;
        while(b>0){
            if(b%2==1){
                b--;
                res = res * a % p;
            }
            b /= 2;
            a = a * a % p;
        }
        return res;
    }
}