E2. Сумма НОК (сложная версия)
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
We are sum for we are many
Some Number

Это сложная версия задачи. Разница между простой и сложной версиями задачи заключается только в ограничении на $$$t$$$. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Вам даны два целых положительных числа $$$l$$$ и $$$r$$$.

Посчитайте количество уникальных троек целых чисел $$$(i, j, k)$$$ таких, что $$$l \le i < j < k \le r$$$ и $$$\operatorname{lcm}(i,j,k) \ge i + j + k$$$.

Здесь $$$\operatorname{lcm}(i, j, k)$$$ означает наименьшее общее кратное (НОК) целых чисел $$$i$$$, $$$j$$$, и $$$k$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$\bf{1 \le t \le 10^5}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le 2 \cdot 10^5$$$, $$$l + 2 \le r$$$).

Выходные данные

Для каждого набора входных данных выведите единственное целое число — количество уникальных троек целых чисел, подходящих под условия задачи.

Пример
Входные данные
5
1 4
3 5
8 86
68 86
6 86868
Выходные данные
3
1
78975
969
109229059713337
Примечание

В первом наборе входных данных существует $$$3$$$ подходящих тройки:

  • $$$(1,2,3)$$$,
  • $$$(1,3,4)$$$,
  • $$$(2,3,4)$$$.

Во втором наборе входных данных существует только $$$1$$$ подходящая тройка:

  • $$$(3,4,5)$$$.