Description

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

Input Format

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

Output Format

对于每组数据，输出一个结果，表示$a^{b_i}_imodp_i$的值。
每个结果占一行。

2
3 2 5
4 3 9

4
1

Hint

1≤n≤100000,
$1≤a_i,b_i,p_i≤2×10^9$

Source

2.4数学知识 快速幂