CF2277D2 Number Operating (Hard Version)

[Harry Styles - Carla's Song](https://open.spotify.com/track/3QuRLv8zkIYH31O5VgEpmo) 这是该问题的困难版本。本版本与其他版本的区别在于，所有测试用例中 $r - l + 1$ 之和没有任何限制。 你有一个变量 $x$，初始值为 $0$。每次操作，你可以选择以下两种操作中的一种： - 操作 $1$：将 $2^k$ 加到 $x$，其中 $k$ 为在此之前连续执行操作 $1$ 的次数（特别地，如果这是第一次操作或上一次操作为操作 $2$，则 $k=0$）； - 操作 $2$：将 $x$ 减去 $1$（结果可以为负数）。 对于非负整数 $n$，记 $f(n)$ 为使 $x$ 恰好等于 $n$ 所需的最少操作次数。你可以证明这总是可行的。 现在给定两个整数 $l$ 和 $r$，请计算 $\sum\limits_{n = l}^{r} f(n)$。由于答案可能非常大，请对 $998\,244\,353$ 取模后输出。

每个测试点包含多个测试用例。第一行包含测试用例个数 $t$ （$1 \le t \le 10^4$）。接下来的每个测试用例包含一行，含两个整数 $l$ 和 $r$（$0 \le l \le r \le 10^{18}$）。

对于每个测试用例，输出一行一个整数，即 $\sum\limits_{n = l}^{r} f(n)$ 对 $998\,244\,353$ 取模后的结果。

在第一个测试用例中，$l = r = 4$。初始状态 $x = 0$。一种可以达到最优的 6 步操作序列如下： 1. 执行操作 $1$，此时 $k = 0$，所以 $x$ 变为 $0 + 2^0 = 1$。 2. 再次执行操作 $1$，此时 $k = 1$，$x$ 变为 $1 + 2^1 = 3$。 3. 再次执行操作 $1$，此时 $k = 2$，$x$ 变为 $3 + 2^2 = 7$。 4. 执行操作 $2$，$x$ 变为 $7 - 1 = 6$。 5. 再次执行操作 $2$，$x$ 变为 $6 - 1 = 5$。 6. 再次执行操作 $2$，$x$ 变为 $5 - 1 = 4$。 可以证明无法用 $5$ 步或更少的操作让 $x = 4$，所以 $f(4) = 6$，故答案为 $6$。 在第二个测试用例中，$l = 1$，$r = 3$，有 $f(1) = 1$、$f(2) = 3$、$f(3) = 2$，所以答案为 $1 + 3 + 2 = 6$。 在第三个测试用例中，$l = r = 127$，连续执行 $7$ 次操作 $1$ 可以使 $x = 2^7 - 1 = 127$。可以证明无法用 $6$ 步或更少的操作得到 $x = 127$，所以 $f(127) = 7$，答案为 $7$。 由 ChatGPT 5 翻译