import java.io.Console;
import java.util.Scanner;
public class Main {
 
        static long rozloz(long b,long x,long n){ 
            
                   int i;
                long result = 1; 
                   for(i=0;b!=0;i++){ 
                      if(b % 2 != 0){ 
                         result*=x; 
                         result = result % n; 
                      } 
                      x = x * x; 
                      x = x % n; 
                      b = b/2; 
                   } 
                   return result; 
                } 
        
        public static void main(String[] args) {
 
                 Scanner input = new Scanner(System.in);
 
                 //
                 long n, x, t, b, j; 
                    
                   t = input.nextLong();
                   j=0; 
                   while(j<t){ 
                      //scanf("%d %d %d",&x,&b,&n); 
                           x = input.nextLong();
                           b = input.nextLong();
                           n = input.nextLong();                         
                           x=x%n; 
                      //printf("%d\n",rozloz(b,x,n)); 
                      System.out.println(rozloz(b,x,n));
                           j++; 
                   } 
                 
        }
 
}