POLSKI SPOJ

Liczby pierwsze to takie liczby naturalne, które są większe od 1 i mają dokładnie dwa dzielniki (dzielą się tylko przez jeden i przez samą siebie). Pojęcie to nie jest trudne i uczy się o o tym już w szkole podstawowej, jednakże największe umysły matematyczne nie uporały sobie ze znalezieniem ogólnego wzoru na nie. Takie sławy jak Pierre de Fermat, Martin Mersenne, Leonhard Euler czy Johann Carl Friedrich Gauss zmagali się z tymi wspaniałymi liczbami tworząc często błędne Hipotezy. Na szczęście twoje zadanie nie będzie aż tak skomplikowane. Dziś zajmiemy się liczbami naturalnymi, które nie są pierwsze. Napisz program, który określi, jaki jest maksymalny podzbiór kolejnych liczb naturalnych należących do przedziału obustronnie domkniętego, które nie są pierwsze.

Wejście

W pierwszym wierszu jedna liczba n określająca ilość zestawów danych (0 < n ≤10⁵). Każdy zestaw składa się z dwóch liczb a, b reprezentujących przedział [a, b], gdzie 0 ≤ a ≤ b ≤ 4⋅10⁶.

Wyjście

Dla każdego zestawu znajdź największy spójny podciąg kolejnych liczb naturalnych, które nie są pierwsze

Przykład

Wejście:
3
1 10
10 10000
20 22

Wyjście:
3
35
3