F2. Maximum Flow in DIV3?(Hard Version)
time limit per test
6 s
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only difference between the two versions are the constraints on $$$l$$$ and $$$r$$$.

There is a flow network with $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$.The source node is vertex $$$1$$$, and the sink node is vertex $$$n$$$.

The following condition holds:

  • For every distinct positive integers $$$a$$$, $$$b(1\leq a,b \leq n)$$$,if $$$a$$$ is divided by $$$b$$$, then there is an edge from node $$$b$$$ to node $$$a$$$, with capacity $$$\frac{a}{b}$$$.

Calculate the sum of the maximum flow of the flow network, in all $$$n \in [l,r]$$$, mod $$$998244353$$$.

i.e) Let's call the maximum flow of $$$n = i$$$ by $$$flow(i)$$$, Then you should calculate the $$$ \left( \sum_{i=l}^r flow(i) \right)\mod 998244353 $$$.

Input

The first line of the input contains an integer $$$t (1 \le t \le 100)$$$ — the number of test cases.

Then follow the descriptions of the test cases.

Each test case consists of one line, contains two integers $$$l$$$ and $$$r$$$ $$$(2 \le l \le r \le 10^{14})$$$ — described in statement.

The sum of $$$r$$$ over all test cases does not exceed $$$10^{14}$$$.

Output

Print out $$$t$$$ lines, each of which is the answer to the corresponding test case.

Example
Input
3
2 3
6 9
10 15
Output
5
41
99