## TAMADOM - PKP Knows Nothing 2

no tags

"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 NRM, 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 NR 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
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 ]

 Added by: Avik Sarkar Date: 2018-05-30 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All Resource: RUET Beginner Battle -1