小明想要知道$a^b$的值，但是这个值会非常的大。

所以退而求其次，小明想让你帮他求出来$(a^b) \% c$的值。

第一行为一个数$n$，表示有$n$组数据。

每组数据有三个整数$a$,$b$,$c$。

$1 \leq a,b,c \leq 50000$

$1 \leq n \leq 1100$

每组数据有一行输出：输出$(a^b) \%c $。

 #include<stdio.h>

 int main()

 {

     int n,a,b,c,i;

     scanf("%d",&n);

     while(n--)

     {

         scanf("%d %d %d",&a,&b,&c);

         int ans,t;

         t=a;

         for(i=;i<b;i++)

           {    ans=t%c;

               t=ans*a;

           }

         printf("%d\n",ans);

     }

     return ;

 }