using System;

public class Program

{

    public static void Main()

    {

        int i,j,t;

        int x,y,m,k=1;

        t=int.Parse(Console.ReadLine());

        for(i=0;i<t;i++)

        {

            x=int.Parse(Console.ReadLine());

            y=int.Parse(Console.ReadLine());

            m=int.Parse(Console.ReadLine());

        for(j=1;j<=y;j++)

        {

            k=x*k;

        }

        k=k%m;

        Console.WriteLine("{0}",k);

        }

    }

}