Description

给出组合数C(n,m)，表示从n个元素中选出m个元素的方案数。例如 C(5,2)=10;C(4,2)=6。可是，当n，m比较大的时候，C(n,m)很大！于是，小波希望你能输出 C(n,m) mod p 的值。

Format

Input

输入数据第一行是一个正整数T,表示数据组数 (T <= 100) 接下来是T组数据，每组数据有3个正整数 n, m, p (1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素数)

Output

对于每组数据，输出一个正整数，表示C(n,m) mod p的结果。

Sample 1

Input

2
5 2 3
5 2 61

Output

1
10

【提示】 Lucas 定理模板题

Limitation

1s, 32MiB for each test case.