题目描述

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

输入

第一行包含整数 $n$。 接下来 $n$ 行，每行包含三个整数 $ai,bi,pi$。

输出

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

样例输入

2
3 2 5
4 3 9

样例输出

4
1

提示

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