Горилла и леопардик
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
32 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Факториалом целого положительного числа $$$n$$$ называется число $$$n! = 1 \cdot 2 \cdot \ldots \cdot n$$$.

Леопардовым называется число, представимое в виде произведения факториалов. Например, число $$$2880$$$ является леопардовым ($$$2! \cdot 2! \cdot 3! \cdot 5!$$$).

Горилловым называется число, представимое в виде суммы ровно трёх леопардовых чисел. Например, число $$$342$$$ является горилловым ($$$6 + 96 + 240$$$).

Красотой гориллового числа называется количество упорядоченных способов представить его в виде суммы трёх леопардовых чисел. Заметьте, что представления $$$6 + 96 + 240$$$ и $$$96 + 6 + 240$$$ считаются различными. Например, красота гориллового числа $$$6$$$ равна $$$4$$$ ($$$1 + 1 + 4$$$, $$$1 + 4 + 1$$$, $$$2 + 2 + 2$$$, $$$4 + 1 + 1$$$).

Вам предстоит ответить на $$$q$$$ запросов.

Каждый запрос задаёт отрезок целых чисел $$$[l \ldots r]$$$. Посчитайте сумму красот горилловых чисел $$$x$$$ на этом отрезке ($$$l \le x \le r$$$).

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

В первой строке дано целое число $$$q$$$ ($$$1 \le q \le 5000$$$) — количество запросов.

В следующих $$$q$$$ строках даны целые числа $$$l, r$$$ ($$$1 \le l \le r \le 10^9$$$) — отрезок запроса.

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

Выведите $$$q$$$ целых чисел — ответ для каждого запроса.

Пример

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

    41 677 100500150 14441 1000000000

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

    11
    878262
    27713
    133806210

Примечание