La sucesión de Fibonacci se define mediante la siguiente relación de recurrencia:

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

con los valores iniciales $F_0=0$ y $F_1=1$.

Los primeros valores de la sucesión de Fibonacci son $0,1,1,2,3,5,8,13,21,\ldots$.

Sea:

• $G(1,n)$ el $n$-ésimo número de Fibonacci.

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

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

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

Entrada

La primera línea de la entrada contiene un único entero $T$: el número de casos de prueba ($1\le T\le10^5$).

Cada caso de prueba consta de una línea que contiene tres enteros $n$, $k$ y $p$, separados por espacios simples ($1\le k,n\le10^{18}$, $1\le p\le10^6$).

Salida

Para cada caso de prueba, imprime una línea que contenga $G(k,n)\bmod p$.

Ejemplos

Entrada 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

Salida 1

1
1
1
1
1
1
2
1
1
890625