The Joker has played his cards again. This time he has chosen to attack DCE Coders. Gitanshu, and other coders have been abducted.

Mishra has solved the first part of the riddle and estimated N locations. Now, it's upto you to choose R locations among these N.

Calculate the number of ways you can chose the R locations . Since the answer can be large calculate the answer modulo M .

Input

First line contains T number of testcases .

Each line contains 3 integers N,R,M . 

Output

Output the required answer

Constraints

1 <= T <= 10⁴

1 <= M <= 10⁹

1 <= R <= N <= 10⁹

M is a square-free number having prime factors less than 50 .

Example

Input:
4
5 2 1001
5 2 6
20 6 210
13 4 39

Output:
10
4
120
13