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$.

2
1 5 2
2 5 3

0
2