给定 $n$ 组 $a_i,b_i,p_i$，对于每组数据，求出 $a_i^{b_i} \bmod p_i$ 的值。
输入格式
第一行包含整数 $n$。
接下来 $n$ 行，每行包含三个整数 $a_i,b_i,p_i$。
输出格式
对于每组数据，输出一个结果，表示 $a_i^{b_i} \bmod p_i$ 的值。
每个结果占一行。
数据范围
$1 \le n \le 100000$,
$1 \le a_i,b_i,p_i \le 2×10^9$
样例输入
2
3 2 5
4 3 9
样例输出
4
1
提示
