编程题：幂次取余

给定三个正整数A，B和C，求$$A^B$$ mod C的结果，其中mod表示求余数。

### 输入格式:

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据输入三个正整数A，B，C（A，B，C≤1000000）。

### 输出格式:

对于每组测试，输出计算后的结果，每组测试的输出占一行。

### 输入样例:

in
2
3 3 5
4 4 6



### 输出样例:

out
2
4








答案：若无答案欢迎评论