Rikka with Segment Tree

Rikka is a master of data structures and Segment tree is Rikka's favorite data structure. This problem is a simple exercise about it.

Given a positive integer $n$, the segment tree on $[1,n]$ can be built by a recursive process: Starting with $[1,n]$, suppose the current interval is $[l,r]$, the process recursively builds subtrees for $\left[l, \left \lfloor \frac{l+r}{2} \right\rfloor\right], \left[ \left \lfloor \frac{l+r}{2} \right \rfloor + 1, r \right]$ until $l = r$.

For example, when $n=5$, there are $9$ intervals on the segment tree: $[1,1],[2,2],[3,3],[4,4],[5,5],[1,2],[4,5],[1,3],[1,5]$.

To explore the structure of segment trees, Rikka defines a magic function $f(i,n)$ which represents the depth of node $[i,i]$ on a segment tree on $[1, n]$ (the depth of the root is defined as $1$). For example, $f(1,5)=f(2,5)=4,f(3,5)=f(4,5)=f(5,5)=3$.

Now Rikka gives you two positive integers $L,R(L \leq R)$, and she wants you to calculate:
$$
\sum_{n=L}^R \sum_{i=1}^n \left(f(i,n) \times i \right)
$$

The first line of the input contains a single integer $T(1 \leq T \leq 1000)$, the number of test cases.

For each test case, the input contains a single line with two positive integers $L,R(1 \leq L \leq R \leq 10^{18})$.

For each test case, output a single line with a single integer, the answer. The answer may be very large, you only need to output the answer modulo $998244353$.

5
4 4
1 4
1 10
1 100
1 1000

30
52
843
1236922
763123843

2019 Multi-University Training Contest 9