Waiter: Good day, sir! What would you like to order?

Lucas: One Cheese & Random Toppings (CRT) pizza for me, please.

Waiter: Very good, sir. There are $N$ toppings to choose from, but you can choose only ${R}$ toppings.

Lucas: Hmm, let's see...

...Then Lucas started writing down all the ways to choose R toppings from N toppings in a piece of napkin. Soon he realized that it's impossible to write them all, because there are a lot. So he asked himself: How many ways are there to choose exactly ${R}$ toppings from $N$ toppings?

Since Lucas doesn't have all the time in the world, he only wished to calculate the answer modulo ${M}$, where M is a squarefree number whose prime factors are each less than 50.

Fortunately, Lucas has a Wi-Fi-enabled laptop with him, so he checked the internet and discovered the following useful links:

Lucas' theorem

Chinese remainder theorem (CRT)

Input Format

The first line of input contains ${T}$, the number of test cases. The following lines describe the test cases.

Each test case consists of one line containing three space-separated integers: $N$, ${R}$ and ${M}$.

Constraints

$1\leq T\leq200$

$1\leq M\leq10^9$

$1\leq R\leq N\leq10^9$

${M}$ is squarefree and its prime factors are less than $50$

Output Format

For each test case, output one line containing a single integer: the number of ways to choose ${R}$ toppings from $N$ toppings, modulo ${M}$.

Sample Input

6
5 2 1001
5 2 6
10 5 15
20 6 210
13 11 21
10 9 5

Sample Output

10
4
12
120
15
0

Explanation

Case 1 and 2: Lucas wants to choose 2 toppings from 5 toppings. There are ten ways, namely (assuming the toppings are A, B, C, D and E):

AB, AC, AD, AE, BC, BD, BE, CD, CE, DE

Thus,

Case 1: $10\:{mod}\:1001=10$

Case 2: $10\:{mod}\:6=4$

Case 6: We can choose 9 toppings from 10 by removing only one from our choice. Thus, we have ten ways and $10\:{mod}\:5=0$

见题面

见题面