Rikka with Segment Tree

Problem Description

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) $$

Input

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})$.

Output

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$.

Sample Input

5

4 4

1 4

1 10

1 100

1 1000

Sample Output

30

52

843

1236922

763123843

Source

2019 Multi-University Training Contest 9