Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×
D2. Операции с числами (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Harry Styles - Carla's Song

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии ограничение на сумму $$$r - l + 1$$$ по всем наборам входных данных отсутствует.

У вас есть переменная $$$x$$$, изначально равная $$$0$$$. За одну операцию вы можете выполнить одно из следующих действий:

  • Операция $$$1$$$: прибавить $$$2^k$$$ к $$$x$$$, где $$$k$$$ — количество раз, которое операция $$$1$$$ была выполнена подряд непосредственно перед текущей (в частности, $$$k = 0$$$, если это первая операция или предыдущей была операция $$$2$$$);
  • Операция $$$2$$$: вычесть $$$1$$$ из $$$x$$$ (результат может быть отрицательным).

Для неотрицательного целого числа $$$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$$$.

Пример
Входные данные
5
4 4
1 3
127 127
0 1000
999999999999900001 1000000000000000000
Выходные данные
6
6
7
25383
102936941
Примечание

В первом наборе входных данных $$$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$$$.
Можно показать, что получить $$$x = 4$$$ за $$$5$$$ или меньше операций невозможно. Поэтому $$$f(4) = 6$$$, и ответ равен $$$6$$$.

Во втором наборе входных данных $$$l = 1$$$ и $$$r = 3$$$. Имеем $$$f(1) = 1$$$, $$$f(2) = 3$$$ и $$$f(3) = 2$$$. Поэтому ответ равен $$$1 + 3 + 2 = 6$$$.

В третьем наборе входных данных $$$l = r = 127$$$. Можно выполнить операцию $$$1$$$ семь раз подряд и получить $$$x = 2^7 - 1 = 127$$$. Можно показать, что получить $$$x = 127$$$ за $$$6$$$ или меньше операций невозможно. Поэтому $$$f(127) = 7$$$, и ответ равен $$$7$$$.