"You know nothing, PKP Snow"

PKP Snow is tired of hearing this. Now he wants to prove that he does know something!

He has N distinct dragonglass knives in front of him. He needs to choose R knives out of these. Everyone thinks PKP doesn't know how many ways he can choose R knives out of N. Help PKP finding the answer and thus prove them wrong. But the answer can be very big, so PKP will tell the answer modulo M.

Given N, R, M, your job is to find the answer for PKP.

Input

Input starts with an integer T, denoting the number of test cases. Then each of next T lines contains three integers N, R and M.

Constraints

1 <= T <= 100

1 <= N <= 100000

0 <= R <= 100000

1 <= M <= 1000000000000

Output

For each test case, print the answer PKP has to find, number of ways to choose R knives out of N modulo M. Print each answer in separate lines like in sample output.

Example

Input:
5
5 3 100
5 3 2
5 3 7
1 1 20
100 50 1000000009

Output:
10
0
3
1
933591892

Explanation

PKP can choose 3 knives out of 5 knives in 10 ways. 10 modulo 100 is 10, while 10 modulo 7 is 3. A modulo B means the remainder found after dividing A by B.

[Original Setter of this problem is Tahsin Masrur, RUET ]