D2. Number Operating (Hard Version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Harry Styles - Carla's Song

This is the hard version of the problem. The difference between the versions is that in this version, there is no constraint on the sum of $$$r - l + 1$$$ over all test cases.

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

Output

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

Example
Input
5
4 4
1 3
127 127
0 1000
999999999999900001 1000000000000000000
Output
6
6
7
25383
102936941
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$$$.