Power Tower

問題文

正整数 $N, M, K$ が与えられます。 $\underbrace{N^{N^{N^{⋰^{N}}}}}_{M\text{ 個の }N}$ を $K$ で割った余りを求めてください。

ただし、べき乗は右上から順に計算します。すなわち整数 $a, b, c$ について、 $a^{b^{c}} = a^{(b^c)}$ と定義されます。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力される値はすべて整数
• $1 \leq T \leq 1000$
• $1 \leq N, M \leq 10^{18}$
• $2 \leq K \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

各テストケースは以下の形式で与えられる。

出力

答えを出力せよ。

入力例 1

3
2 3 100
100 10 998244353
1000000000000000000 1000000000000000000 100000000

出力例 1

16
515592166
0

$1$ 番目のテストケースについて、 $2^{2^2} = 2^4 = 16$ です。これを $100$ で割った余りは $16$ です。