华华教月月做数学 题解

import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static long num[] = new long[1023];
    public static int k=0;
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T -- > 0) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            long mod = sc.nextLong();          
             
            System.out.println(pow(a , b , mod) % mod);
        }
    }
    public static long pow(long A,long B,long P)
    {
        long temp=1;
        while(B>0)
        {
            if((B&1)==1)
            {
                temp=cheng(temp,A,P);
            }
            A= cheng(A,A,P);
            B>>=1;
        }
        return temp;
    }
   public static long cheng(long a, long b,long P)
   {
    long ans = 0;
    while (b > 0)
    {
        if ((b & 1) != 0)
        {
            ans =(ans+ a)%P;
        }
        b >>= 1;
        a = (a+a)%P;
    }
    return ans;
  }
                  }