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 ~998\,244\,353~.

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 ~998\,244\,353~.

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