The Alchemist gives you a very simple problem, calculate ${N \choose R}$%M

Input:

The first line of input contains an integer T denoting the number of test cases .

Each line of test case contains 3 space separated integers N, R and M

Output:

For each test case, output the required answer in a new line.

Constraints:

$1\le T \le 100$

$1\le M \le 10^5$

M is square free and its largest prime factor is less than $50$

Subtask 1: $10$ Points

$1\le R \le N \le 10$

Subtask 2: $20$ Points

$1\le R \le N \le 100$

Subtask 3: $70$ Points

$1\le R \le N \le 10^5$