次方求模

题目描述

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

输入说明

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

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

输出说明

每组测试数据结果占一行

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

样例

输入

2
2 3 5
3 10 10

输出

3
9

提示

作者：卢家品