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 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