ZCC loves hacking

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 262144/131072 K (Java/Others)

Description

Now, a Codefires round is coming to end. ZCC has got $C(0\leq C\leq 10^6)$ points by solving all problems. He is amazed that all other contestants in his room have also solved the hardest problem. So he concludes that most contestants are gonna get FST after the contest except the top rated coder Memset137. Before that, ZCC will hack them to make his score higher. There are $N(1\leq N\leq 100000)$ other contestants in ZCC's room. They are sorted by their ratings(So Memset137 is the N-th contestant). When ZCC successfully hacks the i-th contestant, he will get i points. You may assume ZCC can hack every wrong solution in very little time, and Memset137 is the contestant with number N. During that time, other contestants won't bother him.

Since ZCC is a modest winner, he doesn't want his score to be too high. ZCC wonders how many ways are there that he can choose some contestants' solutions except the one submitted by Memset137 and hack them so that his final score is between $L$ and $R$$(C\leq L\leq R< C+N)$.

Obviously the result can be very large, so please output it modulo 998244353.

Input

The first line contains an integer $T(T=100)$ which denotes the number of test cases.
For each test case, there will be four integers $N(N\leq 10^5)$, $C$, $L$, $R$ in a single line.

For 95% of the test cases, $N\leq 2000$.
For 97% of the test cases, $N\leq 50000$.

Output

For each test case, print a single integer which is the answer.

Sample Input

3 3 0 1 2 5 13 14 17 100 0 23 59

Sample Output

2 6 90567

Hint

hujie

Source

BestCoder Round #41

提交代码