Background

Even if I, CYJian, were to die, die outside, or jump off from here, I would still not eat a single bite of cafeteria food.

Problem Description

On day $i$, the cafeteria has $i$ dishes. CYJian thinks the tastiness of the $j$-th dish on day $i$ is $\left\{\dfrac{i}{j}\right\}$ (where $\{\}$ means taking the fractional part). Of course, CYJian is someone who likes to try things, so he will eat a little of every dish.

Now CYJian has $T$ queries. Each query asks for the total tastiness gained from day $A _ i$ to day $B _ i$. Please help him compute it. Output the answer modulo $998244353$.

Input Format

The first line contains an integer $T$.

The next $T$ lines each contain two integers, representing $A$ and $B$ for each query.

Output Format

Output $T$ lines, each containing a positive integer representing the sum of tastiness.

If the answer can be written as $\dfrac{P}{Q}$, then you need to find any $x$ such that $Q \times x \equiv P \pmod{998244353}$, and output $x \bmod 998244353$.

1
1 3

499122177

Hint

Sample Explanation

On day 1 the tastiness is $0.00$. On day 2 the tastiness is $0.00+0.00=0.00$. On day 3 the tastiness is $0.00+0.50+0.00=0.50$. Thus $0.00+0.00+0.50=0.50=\dfrac{1}{2}$. Since $499122177 \times 2 \equiv 1 \pmod{998244353}$, the answer is $499122177$.

Constraints

This problem uses bundled testdata.

Translated by ChatGPT 5