CF2277D2 Number Operating (Hard Version)

[Harry Styles - Carla's Song](https://open.spotify.com/track/3QuRLv8zkIYH31O5VgEpmo) 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 $ .

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

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

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