Leo searched for a new fib-like problem, and ...
it's not a fib-like problem that he found !!! Here it is.

Let FIB the Fibonacci function :
FIB(0)=0 ; FIB(1)=1
and
for N>=2 FIB(N) = FIB(N-1) + FIB(N-2)

Example : we have FIB(6)=8, and FIB(8)=21.

Let F(K, N) a new function:
F(0, N) = N for all integers N.
F(K, N) = F(K-1, FIB(N) ) for K>0 and all integers N.

Example : F(2, 6) = F(1, FIB(6) ) = F(0, FIB( FIB(6) ) ) = FIB( FIB(6) ) = FIB(8) = 21

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are three integers: K, N, M.

Output

For each test case, print F(K, N),
as the answer could not fit in a 64bit container,
give your answer modulo M.

Example

Input:
3
4 5 1000
3 4 1000
2 6 1000

Output:
5
1
21

Constraints

1 <= T <= 10^3
0 <= K <= 10^18
0 <= N <= 10^18
2 <= M <= 10^18

K, N, M are uniform randomly chosen.

You would perhaps have a look, before, at the medium edition with easier constraints.

Edit(12/I/2015) My old Python code now ends in 2.19s using PY3.4 and cube cluster.

Edit(11/2/2017) Compiler updates ; my old Python3.5 code ends in 0.98s. New TL.