题目描述

一共$T$组数据,每组数据给定 $3$ 个数字 $a,b,p$，对于每组数据，求出 $a^{b}$ % p 的值。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

然后是每组测试用例的描述。

每个测试用例描述为一行，包含$3$ 个整数 $a,b,p$。

数据保证，$1\leq T\leq 500$，$1\leq a,b,p\leq 2 \times 10^{9}$。

输出格式

输出计算结果，每一个结果一行。

样例

2
3 2 5
4 3 9

4
1