Sequence

Problem Description

A good sequence $a_0,a_1,...,a_{tn-1}$ satisfies following criteria:

• $a_0=0,a_{tn-1}=2tn-1,1 \leq a_{k+1}-a_k \leq d\ (0 \leq k < tn-1)$.
• $\forall\ i,j,\ a_j-a_i \not= kn\ (k\ \text{is any odd number, }0 \leq i < j < tn)$ Foreverlasting wants to know the number of good sequence.

Input

The first line contains integer $T\ (1 \leq T \leq 10^4)$ --- the number of test cases. The first line of each test case contains three integers $t,n,d\ (1 \leq d \leq 5 \cdot 10^4, 1 \leq t \leq 10^5, 1 \leq n \leq 10^{15})$. It is guaranteed that the sum of $d$ does not exceed $2 \cdot 10^5$.

Output

For each case, output the number of good sequence modulo $998244353$.

Sample Input

2
1 5 2
2 5 3

Sample Output

0
2

Source

2023“钉耙编程”中国大学生算法设计超级联赛（9）