题解 | #快速幂#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int q = in.nextInt();
        long[][] nums = new long[q][3];
        for(int i = 0;i < q;i++){
            nums[i][0] = in.nextInt();
            nums[i][1] = in.nextInt();
            nums[i][2] = in.nextInt();
        }
        
        // 由公式（a*b）^ c = a^c * b^c
        for(int i = 0;i < q;i++){
           long res = 1;
           while(nums[i][1] > 0){
                if(nums[i][1] % 2 == 1){
                    nums[i][1]--;
                    res = res * nums[i][0] % nums[i][2];
                }
                nums[i][1] /= 2;
                nums[i][0] = nums[i][0] * nums[i][0] % nums[i][2];
           }
           System.out.println(res);
        }
    }
}