D. Array Forge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is an array $$$a$$$. Initially, $$$a = [0]$$$.

Assume that you can perform several operations. In the $$$i$$$-th operation, you can do exactly one of the following two operations:

  • Set $$$a_1 := a_1 + 1$$$;
  • Choose an index $$$j$$$ ($$$1 \leq j \leq |a|$$$), and insert the value $$$i$$$ after $$$a_j$$$.

You are given $$$q$$$ independent queries. For each query, you are given three integers $$$x$$$, $$$l$$$, and $$$r$$$ ($$$1 \leq$$$ $$$\boldsymbol{x \leq l}$$$ $$$\leq r$$$). Your task is to count the number of distinct arrays $$$a$$$ that satisfy the following conditions:

  • $$$a_1 \leq x$$$;
  • The number of operations performed is in the range $$$[l, r]$$$.

Since the answers may be large, you need to output them modulo $$$998\,244\,353$$$.

Input

The first line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$)  — the number of queries.

Next, there are $$$q$$$ lines, each containing three space-separated integers $$$x$$$, $$$l$$$, and $$$r$$$ ($$$1 \leq \boldsymbol{x \leq l}$$$ $$$\leq r\le 10^6$$$).

Output

For each query, output the answer modulo $$$998\,244\,353$$$ on a new line.

Example
Input
6
1 1 1
1 1 2
2 2 3
3 4 5
800000 900000 1000000
1000000 1000000 1000000
Output
2
6
20
384
146046122
463285462
Note

In the first test case, all the $$$2$$$ possible arrays are:

  • $$$[1]$$$
  • $$$[0,1]$$$

In the second test case, all the $$$6$$$ possible arrays are:

  • $$$[1]$$$
  • $$$[0,1]$$$
  • $$$[1,1]$$$
  • $$$[1,2]$$$
  • $$$[0,1,2]$$$
  • $$$[0,2,1]$$$