#GYM104683F2. Maximum Flow in DIV3?(Hard Version)
Maximum Flow in DIV3?(Hard Version)
Description
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 $.
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}$.
Print out $t$ lines, each of which is the answer to the corresponding test case.
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.
3
2 3
6 9
10 15
5
41
99