While going through her friend’s secret diary, one-day Poga came upon a function. The function f was defined as

            f(n, k) - f(n-1, k) = f(n-1, k-1),
            f(n, 0) = 1
            and f(n, k) = 0 when n < k

Seeing how this is a recursive function, Poga got very scared. To find courage, she remembered 2 of her favorite numbers, N and K. Now she wants to find the value of f(N, K). Being a genius, it was very easy for her. Now she has challenged you to do the same too. As the answer can become very big, you should print the answer modulo M.

Input

Input starts with an integer T, denoting the number of test cases.

Then each of the next T lines contains three integers N, K, and M.

Constraints

1 <= T <= 100

1 <= N <= 10⁵

0 <= K <= 10⁵

1 <= M <= 10¹²

Output

For each test case, print the answer, value of f(N, K) modulo M.

Example

Input:
5
7 4 100
6 3 2
6 3 7
2 2 200
57217 10661734081

Output:
35
0
6
1
0