99991244 - 快速幂
Time Limit : 1 秒
Memory Limit : 128 MB
给定 n 组 a,b,p，对于每组数据，求出 a^b mod p 的值。
数据范围 1≤n≤100000, 1≤a,b,p≤2×10^9
Input
第一行包含整数 n。
接下来 n 行，每行包含三个整数 ai,bi,pi。
Output
对于每组数据，输出一个结果，表示 a^b mod p 的值。
每个结果占一行。
Examples
Input
2 3 2 5 4 3 9
Output
4 1