Number Operating (Easy Version)

Ariana Grande - stay

This is the easy version of the problem. The difference between the versions is that in this version, the sum of $r - l + 1$ over all test cases does not exceed $2 \cdot 10^5$.

You have a variable $x$, initially equal to $0$. In one operation, you can do one of the following:

• Operation $1$: add $2^k$ to $x$, where $k$ is the number of times Operation $1$ has been performed in a row immediately before this one (in particular, $k = 0$ if this is the first operation or the previous operation was Operation $2$);
• Operation $2$: subtract $1$ from $x$ (the result may be negative).

For a non-negative integer $n$, let $f(n)$ be the minimum number of operations needed to make $x$ equal to $n$. It can be shown that this is always possible.

You are given two integers $l$ and $r$. Find $\sum\limits_{n = l}^{r} f(n)$. Since the answer can be very large, output it modulo $998\,244\,353$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line of each test case contains two integers $l$ and $r$ ($0 \le l \le r \le 10^{18}$).

It is guaranteed that the sum of $r - l + 1$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the value of $\sum\limits_{n = l}^{r} f(n)$ modulo $998\,244\,353$.

Note

In the first test case, $l = r = 4$. Initially, $x = 0$. One optimal sequence of $6$ operations is as follows:

1. Perform Operation $1$ with $k = 0$, so $x$ becomes $0 + 2^0 = 1$.
2. Perform Operation $1$ with $k = 1$, so $x$ becomes $1 + 2^1 = 3$.
3. Perform Operation $1$ with $k = 2$, so $x$ becomes $3 + 2^2 = 7$.
4. Perform Operation $2$, so $x$ becomes $7 - 1 = 6$.
5. Perform Operation $2$, so $x$ becomes $6 - 1 = 5$.
6. Perform Operation $2$, so $x$ becomes $5 - 1 = 4$.

It can be shown that $x = 4$ cannot be reached in $5$ or fewer operations. Thus, $f(4) = 6$, and the answer is $6$.

In the second test case, $l = 1$ and $r = 3$. We have $f(1) = 1$, $f(2) = 3$, and $f(3) = 2$. Thus, the answer is $1 + 3 + 2 = 6$.

In the third test case, $l = r = 127$. We can perform Operation $1$ seven times in a row to reach $x = 2^7 - 1 = 127$. It can be shown that $x = 127$ cannot be reached in $6$ or fewer operations. Thus, $f(127) = 7$, and the answer is $7$.

5
4 4
1 3
127 127
0 1000
999999999999900001 1000000000000000000

6
6
7
25383
102936941