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^2
0 <= N <= 10^9
2 <= M <= 10^9

You would perhaps have a look, after, at the hard edition with more difficult constraints.

Edit 2017-02-11, after compiler update. My old Python code ends in 0.08s. New TL.