\begin{problem}{Руки вверх! Ваша песенка спета!}{стандартный ввод}{стандартный вывод}{2 секунды}{256 мегабайт}

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

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

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

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

\begin{center}
\includegraphics{pic4.png}
\end{center}


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

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

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


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


\Example

\begin{example}
\exmpfile{example.01}{example.01.a}%
\end{example}

\end{problem}

