题目描述

求a的b次方对c取余的值

输入格式

第一行输入一个整数n表示测试数据的组数（n<100)

每组测试只有一行，其中有三个正整数a,b,c(1=<a,b,c<=1000000000)

输出格式

每组测试数据结果占一行

输出a的b次方对c取余之后的结果

样例

样例 1

输入：

2
2 3 5
3 10 10

输出：

3
9

提示

作者：卢家品