SP12009 FRSKH - Fibonacci recursive sequences (hard)

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

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.

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