Экипаж «Беды» сделал остановку в Египте. Гангстеры Джулико Бандитто и Де Ля Воро Гангстеритто планируют перехватить футляр со скульптурой в древней пирамиде. За ними охотится суперагент 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