Santa and Banta are buddies. Santa has a good sense of humour, but Banta is unable to or partially understands some jokes.

Now Santa has with him N jokes he wishes to tell to Banta. Due to lack of time, he cannot tell all of them and has to choose R jokes for Banta. The total value of all the jokes he tells Banta is Fibonacci ( ^N C _R ).

Note that, Fibonacci(1)=Fibonacci(2)=1 and
Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2) for n > 2.

However, Banta is unable to comprehend all the jokes. The value of jokes he understands is the total value of all jokes Santa tells Banta modulus some value M.

Given N, R and M, your job is to compute the value of jokes Banta understands.

Input Format

First line contains T ,number of test cases to follow.
Next T lines follows, each line containing 3 space separated integers, N, R and M.

Output Format

The output contains T lines, each having the value of jokes Banta understands.

Constraints

• 0 ≤ N,R ≤ 10⁵
• 1 ≤ M ≤ 10⁷
• Sum of N over all test cases ≤ 10⁵

Sample Input

3
2 2 100
2 1 100
3 1 100

Sample Output

1
1
2