数字操作（困难版）AI (CI翻译)
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.
这是本题的困难版本。两个版本之间的区别在于，在本版本中，不限制所有测试用例的 $r - l + 1$ 之和。AI (CI翻译)
You have a variable $x$, initially equal to $0$. In one operation, you can do one of the following:
你有一个变量 $x$，初始值为 $0$。在一次操作中，你可以执行以下操作之一：AI (CI翻译)
- 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).
- 操作
$1$：将$2^k$加到$x$上，其中$k$是紧接在本次操作之前连续执行操作$1$的次数（特别地，如果这是第一次操作，或者上一次操作是操作$2$，则$k = 0$）； - 操作
$2$：从$x$中减去$1$（结果可能为负数）。
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.
对于非负整数 $n$，令 $f(n)$ 表示使 $x$ 等于 $n$ 所需的最少操作次数。可以证明，这始终是可行的。AI (CI翻译)
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$.
给定两个整数 $l$ 和 $r$。求 $\sum\limits_{n = l}^{r} f(n)$。由于答案可能非常大，请输出答案对 $998\,244\,353$ 取模后的结果。AI (CI翻译)
Input
输入格式
AI (CI翻译)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.
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是各个测试用例的描述。AI (CI翻译)
The only line of each test case contains two integers $l$ and $r$ ($0 \le l \le r \le 10^{18}$).
每个测试用例仅包含一行，其中有两个整数 $l$ 和 $r$（$0 \le l \le r \le 10^{18}$）。AI (CI翻译)
Output
输出格式
AI (CI翻译)For each test case, output a single integer — the value of $\sum\limits_{n = l}^{r} f(n)$ modulo $998\,244\,353$.
对于每个测试用例，输出一个整数——$\sum\limits_{n = l}^{r} f(n)$ 的值对 $998\,244\,353$ 取模后的结果。AI (CI翻译)
Note
说明
AI (CI翻译)In the first test case, $l = r = 4$. Initially, $x = 0$. One optimal sequence of $6$ operations is as follows:
在第一个测试用例中，$l = r = 4$。初始时，$x = 0$。以下是一种由 $6$ 次操作组成的最优操作序列：AI (CI翻译)
- Perform Operation
$1$with$k = 0$, so$x$becomes$0 + 2^0 = 1$. - Perform Operation
$1$with$k = 1$, so$x$becomes$1 + 2^1 = 3$. - Perform Operation
$1$with$k = 2$, so$x$becomes$3 + 2^2 = 7$. - Perform Operation
$2$, so$x$becomes$7 - 1 = 6$. - Perform Operation
$2$, so$x$becomes$6 - 1 = 5$. - Perform Operation
$2$, so$x$becomes$5 - 1 = 4$.
- 执行操作
$1$，其中$k = 0$，于是$x$变为$0 + 2^0 = 1$。 - 执行操作
$1$，其中$k = 1$，于是$x$变为$1 + 2^1 = 3$。 - 执行操作
$1$，其中$k = 2$，于是$x$变为$3 + 2^2 = 7$。 - 执行操作
$2$，于是$x$变为$7 - 1 = 6$。 - 执行操作
$2$，于是$x$变为$6 - 1 = 5$。 - 执行操作
$2$，于是$x$变为$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$.
可以证明，无法在 $5$ 次或更少的操作内得到 $x = 4$。因此，$f(4) = 6$，答案为 $6$。AI (CI翻译)
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$.
在第二个测试用例中，$l = 1$ 且 $r = 3$。我们有 $f(1) = 1$、$f(2) = 3$ 和 $f(3) = 2$。因此，答案为 $1 + 3 + 2 = 6$。AI (CI翻译)
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$.
在第三个测试用例中，$l = r = 127$。连续执行七次操作 $1$，可以得到 $x = 2^7 - 1 = 127$。可以证明，无法在 $6$ 次或更少的操作内得到 $x = 127$。因此，$f(127) = 7$，答案为 $7$。AI (CI翻译)
样例
5
4 4
1 3
127 127
0 1000
999999999999900001 1000000000000000000
6
6
7
25383
102936941
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。