Problem F
Fun with Fibonacci

The Fibonacci sequence is defined by the following recurrence relation:

$F_ n = F_{n - 1} + F_{n - 2}$,

with seed values $F_0 = 0$ and $F_1 = 1$.

The first few values of the Fibonacci sequence are $0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots $

Let:

• $G(1, n)$ denotes the $n$-th Fibonacci number.

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

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

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

Input

The first line of input contains the only integer $T$ — the number of test cases. $(1 \le T \le 10^5)$.

Each test case consists of one line, containing $3$ integers $n$, $k$ and $p$, separated by single spaces. $(1 \le k, n \le 10^{18}, 1 \le p \le 10^6)$.

Output

For each test case, print a single line, containing $G(k, n) \bmod p$.

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

1
1
1
1
1
1
2
1
1
890625