フィボナッチ数列は次の漸化式で定義されます。

$$F_n=F_{n-1}+F_{n-2}.$$

初期値は $F_0=0$ および $F_1=1$ です。

フィボナッチ数列の最初の数項は $0,1,1,2,3,5,8,13,21,\ldots$ です。

次のように定義します。

• $G(1,n)$ は $n$ 番目のフィボナッチ数を表します。

• $G(2,n)=G(1,G(1,n))$，

• $G(i,n)=G(1,G(i-1,n))$。

$G(k,n)\bmod p$ を計算してください。

入力

入力の最初の行には、テストケース数を表す整数 $T$ が一つ含まれます ($1\le T\le10^5$)。

各テストケースは一行からなり、一つの空白で区切られた三つの整数 $n$, $k$, $p$ を含みます ($1\le k,n\le10^{18}$, $1\le p\le10^6$)。

出力

各テストケースについて、$G(k,n)\bmod p$ を一行に出力してください。

入出力例

入力 1

10
1 1 1000000
1 2 1000000
1 3 1000000
2 1 1000000
2 2 1000000
2 3 1000000
3 1 1000000
3 2 1000000
3 3 1000000
1000000000000000000 1000000000000000000 1000000

出力 1

1
1
1
1
1
1
2
1
1
890625