Due to your superlative performance in online school, you've been employed by CodeVax. Your assignment is as such:

There are $N$ seats in a line. These seats must be divided into exactly $Q$ cohorts to reduce the transmission of the virus. Each cohort consists of a contiguous segment of exactly $K$ seats. An arrangement of cohorts is considered to be valid if there is at least $1$ seat between any two cohorts and no cohort overlaps another.

Find the total number of valid arrangements, modulo $998244353$.

Input Specification

The first line will contain the integer $T$, representing the number of test cases.

The next $T$ lines will each contain the integers $N_i$, $K_i$ and $Q_i$ for the $i^{\text{th}}$ test case.

Output Specification

For each test case, output the number of valid arrangements, modulo $998244353$.

Constraints

$1\le N\le {10}^6$

$1\le K\le {10}^6$

$1\le Q\le 5\times {10}^5$

$1\le T\le {10}^5$

Note that you will NOT be required to pass all the samples to receive points.

Subtask 1 [5%]

$1\le T\le 400$

$1\le N\le 400$

$K=1$

$Q=2$

Subtask 2 [15%]

$1\le T\le 100$

$1\le N\le 100$

$1\le Q\le 100$

Subtask 3 [80%]

No additional constraints.

Sample Input 1

4
3 1 1
3 1 2
1 1 2
4 1 2

Sample Output 1

3
1
0
3

Explanation for Sample 1

Let x represent the spots in the line where the cohorts are and let - represent empty spaces in the line:

For the first test case, the valid cohort arrangements are: x--, -x-, and --x.

For the second test case, the only valid cohort arrangement is: x-x.

For the third test case, there are no valid cohort arrangements.

For the fourth test case, the valid cohort arrangements are: x-x-, x--x, and -x-x.

Sample Input 2

2
111 22 9
400 25 6

Sample Output 2

0
586572619