E. Eradication
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

We often simplify the square root of a large integer into radical form; for example, $$$\sqrt{432}=12\sqrt3$$$.

Define the number-theoretic function $$$f(n)=\min\{a \mid n=ab^2,\ a,b\in\mathbb N\}$$$ on $$$\mathbb N$$$. In other words, $$$f(n)$$$ is the smallest natural number $$$a$$$ satisfying the equation. Such an $$$a$$$ always exists.

You are given $$$q$$$ queries, each specifying $$$l$$$ and $$$r$$$. For each query, find $$$\sum_{i=l}^r f(i)$$$ modulo $$$998\,244\,353$$$.

Input

The first line contains an integer $$$q$$$ ($$$1 \le q \le 500$$$), the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^{12}$$$), specifying a query interval.

Output

For each query, output one integer: $$$\sum_{i=l}^r f(i)$$$ modulo $$$998\,244\,353$$$.

Example
Input
4
432 432
1 10
10 15
1 100000000
Output
3
38
66
651260790
Note

Sample 1 Explanation

For the second and third queries, the corresponding values of $$$f$$$ are:

$$$$$$ \begin{array}{c|ccccccccccccccc} n &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\ \hline f(n) &1&2&3&1&5&6&7&2&1&10&11&3&13&14&15 \end{array} $$$$$$

In particular, the third query gives $$$$$$ \sum_{i = 10}^{15}f(i) = f(10) + f(11) + f(12) + f(13) + f(14) + f(15) = 10 + 11 + 3 + 13 + 14 + 15 = 66. $$$$$$