#GYM104683F1. Maximum Flow in DIV3?(Easy Version)
Maximum Flow in DIV3?(Easy Version)
Description
This is the easy 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 = 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 — the maximum flow of given flow network.
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 = 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 — the maximum flow of given flow network.
3
2 2
3 3
6 6
2
3
10
Note
In the first case, the flow network is as follows:
Capacity of edge is written on the edge. In the second case, the flow network is as follows:
In the third case, the flow network is as follows:
