1631: 快速幂
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：100
Solved：36
Description
给定 n 组 ai,bi,pi，对于每组数据，求出 ai ^ bi mod pi 的值。
(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p ) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
a ^ b % p = ((a % p)^b) % p （4）
(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p ) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
a ^ b % p = ((a % p)^b) % p （4）
Input
第一行包含整数 n。
接下来 n 行，每行包含三个整数 ai,bi,pi。
Output
对于每组数据，输出一个结果，表示 ai^bi mod pi 的值。
每个结果占一行。
1≤n≤100000
1≤ai,bi,pi≤2×10^9
Sample Input Copy
2
3 2 5
4 3 9Sample Output Copy
4
1