Ciąg Fibonacciego jest zdefiniowany przez następującą zależność rekurencyjną:

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

z wartościami początkowymi $F_0=0$ i $F_1=1$.

Pierwsze wartości ciągu Fibonacciego to $0,1,1,2,3,5,8,13,21,\ldots$.

Niech:

• $G(1,n)$ oznacza $n$-tą liczbę Fibonacciego.

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

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

Oblicz $G(k,n)\bmod p$.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ — liczbę przypadków testowych ($1\le T\le10^5$).

Każdy przypadek testowy składa się z jednego wiersza zawierającego trzy liczby całkowite $n$, $k$ i $p$, oddzielone pojedynczymi spacjami ($1\le k,n\le10^{18}$, $1\le p\le10^6$).

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $G(k,n)\bmod p$.

Przykład

Wejście 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

Wyjście 1

1
1
1
1
1
1
2
1
1
890625