875. 快速幂

给定$n$组$a_i, b_i, p_i$,对于每组数据,求出$a_i ^ {b_i} mod\ p_i$的值。

输入格式

第一行包含整数$n$。

接下来$n$行,每行包含三个整数$a_i, b_i, p_i$。

输出格式

对于每组数据,输出一个结果,表示$a_i ^ {b_i} mod\ 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