#include<iostream>
#include<cstdio>
#include<stdio.h>
using namespace std;


unsigned long long ptg(unsigned long long a, unsigned long long n, unsigned long long m)
{

  unsigned long long c;

if (n==0)
   { return 1;}

c = ptg(a, n/2, m);

if (n%2==0)
{
return (c*c)%m;
}
else return (c*c*a)%m;


}




int main()
{
	unsigned long long n;
    unsigned long long a;
	unsigned long long x;
	unsigned long long m;
	unsigned long long wynik[1000000];

	scanf("%llu", &x);

	for (int i=0; i<x; i++)
	{
	scanf("%llu",&a);
	scanf("%llu",&n);
	scanf("%llu",&m);

	wynik[i]=(ptg(a, n, m));

	}

	for (int i=0; i<x; i++)
	{

	//cout << wynik[0+i] << endl;

	printf ("%llu", wynik[i]);
	printf ("\n");
	}


	return 0;
}