I. Counting Palindromic Sequences
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For a given integer $$$n$$$, find the number of palindromic sequences of positive integers with a sum of $$$n$$$ that contains at least one occurrence of the number $$$k$$$. Output the answer modulo $$$p$$$, where $$$p$$$ is given in the input.

Input

Each test contains multiple testcases. The first line contains the number of testcases $$$t$$$ ($$$1\leq t\leq 10^6$$$). This is followed by $$$t$$$ lines — the description of the testcases.

Each line contains three integers $$$n$$$, $$$k$$$, and $$$p$$$ ($$$1\leq k\leq n\leq 10^6$$$,$$$10^8\leq p\leq 2\cdot 10^9$$$) — the sum of the sequence, the required number, and the number to take the answer modulo of, respectively. The number $$$p$$$ is guaranteed to be a prime.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

—

Testcases in subtasks are numbered $$$1$$$ to $$$20$$$ with samples skipped.

Test $$$1-10$$$: The sum of $$$n$$$ does not exceed $$$5\cdot 10^3$$$.

Test $$$6-20$$$: No additional constraints.

Each test is worth $$$5$$$ points with samples skipped.

Output

For each test case, print one integer — the desired value modulo $$$p$$$.

Example
Input
4
8 2 998244353
12 12 1999999943
10 4 592538069
42 2 100000007
Output
9
1
7
1999923
Note

For the first sample, $$$[2,2,2,2]$$$, $$$[3,2,3]$$$, and $$$[1,1,2,2,1,1]$$$ are examples of sequences that work. Sequences that do not work include $$$[2,3,2]$$$, $$$[3,3,3]$$$, $$$[2,3,1,1,1]$$$, and $$$[4,4]$$$.

— Problem Idea: dutin Problem Preparation: dutin Occurrences: Novice 7, Advanced 3