UVA - 1230 - MODEX

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

public class Main {

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        StringBuffer sb = new StringBuffer("");
        int num = Integer.parseInt(br.readLine());
        for (int i = 0; i < num; i++) {
            String str[]=br.readLine().split(" ");
            BigInteger x=new BigInteger(str[0]);
            int y=Integer.parseInt(str[1]);
            BigInteger n=new BigInteger(str[2]);
            sb.append(x.modPow(BigInteger.valueOf(y), n)).append("\n");
        }
        System.out.print(sb);
    }
  
}