Combinations and modulos

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Calculate C(n,m) modulo p. P is prime number.
 

Input

The first line contains a number, T.
Next T lines, n, m, p. n, m, p < 10000.
 

Output

The answer.

Sample Input

2
1 2 5
2 1 5

Sample Output

3
3

Hint

 

Source

zhengnanlee