//答案错误，说是只对了一半
import java.io.*;
import java.math.BigInteger;
  
  
public class Main
{
    public static void main(String[] args) {
        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out=new PrintWriter(System.out);
        try {
            in.nextToken();
            int n=(int)in.nval;
            for(int i=0;i<n;i++)
            {
                in.nextToken();
                BigInteger a=BigInteger.valueOf((long) in.nval);
                in.nextToken();
                BigInteger b=BigInteger.valueOf((long) in.nval);
                in.nextToken();
                BigInteger c=BigInteger.valueOf((long) in.nval);
                out.println(a.modPow(b, c));
            }
            out.flush();
            out.close();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}

//ac通过的代码

	import java.io.*;



	import java.math.BigInteger;



	  



	publicclassMain



	{



	    publicstaticvoidmain(String[] args) {



	//      StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));



	        Scanner in=newScanner(System.in);



	        PrintWriter out=newPrintWriter(System.out);



	        intn=in.nextInt();



	        BigInteger a,b,c;



	        for(inti=0;i<n;i++)



	        {



	            a=in.nextBigInteger();



	            b=in.nextBigInteger();



	            c=in.nextBigInteger();



	            out.println(a.modPow(b, c));



	        }



	        out.flush();



	        out.close();



	    }



	}