Руки вверх! Ваша песенка спета!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Экипаж «Беды» сделал остановку в Египте. Гангстеры Джулико Бандитто и Де Ля Воро Гангстеритто планируют перехватить футляр со скульптурой в древней пирамиде. За ними охотится суперагент 00X.

Суперагент детально изучил особенности архитектуры древних пирамид и готов вычислить местоположение гангстеров с помощью эхолокации. Для этого он отправит последовательность ультразвуковых сигналов разной частоты.

Назовём частоту $$$b$$$ следующей за частотой $$$a$$$, если $$$b$$$ — минимальное целое число, большее $$$a$$$, такое что $$$\varphi(a) \lt \varphi(b)$$$. Другими словами, $$$b = \displaystyle\min_{x \in \mathbb{N}}\left(x : \begin{cases}a \lt x \\ \varphi(a) \lt \varphi(x)\end{cases}\right) $$$. Напомним, что $$$\varphi(n)$$$ обозначает значение функции Эйлера от $$$n$$$.

В Египте разрешены только частоты, не меньшие $$$l$$$ и не большие $$$r$$$. Помогите суперагенту определить максимальную возможную длину $$$k$$$ последовательности целых чисел $$$a_1, a_2, \ldots, a_k$$$ ($$$l \le a_i \le r$$$, частота $$$a_{i+1}$$$ является следующей для $$$a_i$$$).

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

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$) — количество наборов входных данных.

В каждом наборе входных данных даны целые числа $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^6$$$) — подотрезок разрешённых частот в Египте.

Обратите внимание, что ограничений на сумму $$$r - l$$$ по всем наборам входных данных нет.

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

Для каждого набора входных данных выведите единственное целое число $$$k$$$ — максимальную длину подходящей последовательности.

Пример

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

    614 181 207 172 271 79177 190

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

    385144