A. Interval and Expected Value
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an integer interval $$$[l,r]$$$. At first, your score $$$sco$$$ is equal to $$$0$$$.

Repeat the following process:

  1. Choose an integer $$$x\in [l,r]$$$ uniformly at random, and update $$$sco := sco + x$$$.
  2. If $$$l=r$$$, stop. Otherwise, replace $$$[l,r]$$$ by a uniformly random proper subinterval of $$$[l,r]$$$ and go back to step 1. In other words, letting $$$len=r-l+1$$$, there are $$$\frac{len(len+1)}{2}-1$$$ proper subintervals of $$$[l,r]$$$, each chosen with equal probability.

Your task is to find the expected value of $$$sco$$$. Output the answer modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The only line of each testcase contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 2 \cdot 10^6$$$).

Output

For each test case, print a single integer — the answer modulo $$$998\,244\,353$$$.

Example
Input
4
2 3
1 1
5 8
1 2000000
Output
5
1
454755778
881266578
Note

In the first test case, the initial interval is $$$[2,3]$$$. The following events occur with equal probability:

  • $$$sco$$$ is increased by $$$2$$$ $$$\rightarrow$$$ $$$[l,r]$$$ becomes $$$[2,2]$$$ $$$\rightarrow$$$ $$$sco$$$ is increased by $$$2$$$ $$$\rightarrow$$$ stop. The final value of $$$sco$$$ is $$$4$$$.
  • $$$sco$$$ is increased by $$$3$$$ $$$\rightarrow$$$ $$$[l,r]$$$ becomes $$$[3,3]$$$ $$$\rightarrow$$$ $$$sco$$$ is increased by $$$3$$$ $$$\rightarrow$$$ stop. The final value of $$$sco$$$ is $$$5$$$.
  • $$$sco$$$ is increased by $$$3$$$ $$$\rightarrow$$$ $$$[l,r]$$$ becomes $$$[2,2]$$$ $$$\rightarrow$$$ $$$sco$$$ is increased by $$$2$$$ $$$\rightarrow$$$ stop. The final value of $$$sco$$$ is $$$5$$$.
  • $$$sco$$$ is increased by $$$3$$$ $$$\rightarrow$$$ $$$[l,r]$$$ becomes $$$[3,3]$$$ $$$\rightarrow$$$ $$$sco$$$ is increased by $$$3$$$ $$$\rightarrow$$$ stop. The final value of $$$sco$$$ is $$$6$$$.

Thus, the expected value of $$$sco$$$ is $$$\frac{4+5+5+6}{4}=5$$$.