Description

The combinatorial number $C(n,m)$ represents the number of ways to choose $m$ elements from a set of $n$ elements. For example, $C(5,2) = 10$ and $C(4,2) = 6$. However, when $n$ and $m$ are relatively large, $C(n,m)$ becomes very large. Therefore, xiaobo asks you to output the value of $C(n,m) \bmod p$.

Input Format

The first line of input is a positive integer $T$, representing the number of test cases;

Next, there are $T$ test cases, each consisting of three positive integers $n, m, p$.

Output Format

For each test case, output a positive integer representing the result of $C(n,m) \bmod p$.

Sample 1

2
5 2 3
5 2 61

1
10

Data Range and Hints

For all data, $T\le 100$, $1\le m\le n\le 10^9$, $m\le 10^4$, $m\lt p\lt 10^9$, and $p$ is a prime number.