package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class main1{
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String line[] = r.readLine().split(" ");
        int n = Integer.valueOf(line[0]);
        for (int i = 0; i <n ; i++) {
            String line2[] = r.readLine().split(" ");
            long a = Integer.valueOf(line2[0]);
            long b = Integer.valueOf(line2[1]);
            long c = Integer.valueOf(line2[2]);
            System.out.println(find(a,b,c));
        }
    }

    public static long find(long x,long y,long z){
        long result = 1;
        long a = x;
        while(y!=0){
            if((int)(y&1)==1){
                result = (result * a) % z;
            }
            y =y>>1;
            a = a * a;
        }
        return result;
    }
}