import java.math.BigInteger;
import java.util.Scanner;
 
public class Main{
 
	public static void main(String[] args) {
	  Scanner sc = new Scanner(System.in);//object create for taken input from user;
	  BigInteger x,y,n,res;// declare x,y,n,res in BigInteger data type for large number calculation;
	  int test;
	  test=sc.nextInt();//Taken testcase for this problem;
	  while(test-->0)//if testcase taken input then it's break;
	  {
		  x=BigInteger.valueOf(sc.nextInt());//taken input of x;
		  y=BigInteger.valueOf(sc.nextInt());//taken input of y;
		  n=BigInteger.valueOf(sc.nextInt());//taken input of n;
		  res=x.modPow(y, n);// pow(x,y)%n operation are perform;
		  System.out.println(res);//final result are print;
	  }
 
	}
 
}
 

CgppbXBvcnQgamF2YS5tYXRoLkJpZ0ludGVnZXI7CmltcG9ydCBqYXZhLnV0aWwuU2Nhbm5lcjsKCnB1YmxpYyBjbGFzcyBNYWluewoKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKCSAgU2Nhbm5lciBzYyA9IG5ldyBTY2FubmVyKFN5c3RlbS5pbik7Ly9vYmplY3QgY3JlYXRlIGZvciB0YWtlbiBpbnB1dCBmcm9tIHVzZXI7CgkgIEJpZ0ludGVnZXIgeCx5LG4scmVzOy8vIGRlY2xhcmUgeCx5LG4scmVzIGluIEJpZ0ludGVnZXIgZGF0YSB0eXBlIGZvciBsYXJnZSBudW1iZXIgY2FsY3VsYXRpb247CgkgIGludCB0ZXN0OwoJICB0ZXN0PXNjLm5leHRJbnQoKTsvL1Rha2VuIHRlc3RjYXNlIGZvciB0aGlzIHByb2JsZW07CgkgIHdoaWxlKHRlc3QtLT4wKS8vaWYgdGVzdGNhc2UgdGFrZW4gaW5wdXQgdGhlbiBpdCdzIGJyZWFrOwoJICB7CgkJICB4PUJpZ0ludGVnZXIudmFsdWVPZihzYy5uZXh0SW50KCkpOy8vdGFrZW4gaW5wdXQgb2YgeDsKCQkgIHk9QmlnSW50ZWdlci52YWx1ZU9mKHNjLm5leHRJbnQoKSk7Ly90YWtlbiBpbnB1dCBvZiB5OwoJCSAgbj1CaWdJbnRlZ2VyLnZhbHVlT2Yoc2MubmV4dEludCgpKTsvL3Rha2VuIGlucHV0IG9mIG47CgkJICByZXM9eC5tb2RQb3coeSwgbik7Ly8gcG93KHgseSklbiBvcGVyYXRpb24gYXJlIHBlcmZvcm07CgkJICBTeXN0ZW0ub3V0LnByaW50bG4ocmVzKTsvL2ZpbmFsIHJlc3VsdCBhcmUgcHJpbnQ7CgkgIH0KCgl9Cgp9Cg==

MiAKMiAzIDUgCjIgMjE0NzQ4MzY0NyAxMyAKMA==

2 
2 3 5 
2 2147483647 13 
0