Problem description

Ostatnio na lekcji matematyki w szkole podstawowej Jasio poznał pierwiastkowanie liczb. Był bardzo zafascynowany tym tematem, więc gdy tylko przyszedł do domu zabrał się za odrabianie zadania domowego. W zeszycie ćwiczeń znajdowało się zadanie z gwiazdką. Musisz pamiętać, że Jasio jest w podstawówce i zna tylko liczby naturalne (większe lub równe 0). Zadanie brzmiało następująco:

Liczbę naturalną n nazywamy niepierwiastkowlną, gdy nie istnieje taka liczba naturalna k > 1, że $\sqrt[k]{n}$ jest liczbą naturalną. Dla każdego podpunktu napisz, ile jest liczb niepierwiastkowalnych w przedziale liczb naturalnych od l do r włącznie.}

Jasio siedzi nad zadaniem domowym już bardzo długo i wciąż nie udało mu się go rozwiązać, a zadanie ma bardzo dużo podpunktów. Z drugiej strony Jasio chciałby jutro pochwalić się pani od matematyki, że zrobił zadanie z gwiazdką. A może Ty mu w tym pomożesz?

Napisz program, który: wczyta opis podpunktów z zeszytu ćwiczeń Jasia, dla każdego przedziału policzy ile jest w nim liczb niepierwiastkowalnych i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba naturalna T, oznaczająca liczbę podpunktów w zeszycie ćwiczeń Jasia. W każdym z kolejnych T wierszy znajdują się dwie liczby naturalne L_i, R_i, oddzielone pojedynczym odstępem, oznaczające granice przedziału, dla którego szukamy liczb niepierwiastkowalnych.

Wyjście

Twój program powinien wypisać na wyjście dokładnie T wierszy. W i-tym z nich powinna znaleźć się jedna liczba naturalna, będąca odpowiedzią na i-ty podpunkt z zadania Jasia.

Ograniczenia

1 ≤ T ≤ 10 000, 1 ≤ L_i ≤ R_i ≤ 10¹⁸.

Przykład

2
2 10
2045 2050

6
5