Jeszcze kilka dni temu Jasiowi śniły się głównie liczby pierwsze. Dziś, interesują go już tylko pewne specyficzne liczby złożone. Jasio nazywa liczbę złożoną liczbą znaczącą, jeżeli średnia arytmetyczna wszystkich dzielników właściwych tej liczby (tj. z wyłączeniem jedności i jej samej) nie przekracza pierwiastka z tej liczby. Przykładowo, 4 jest liczbą znaczącą, ale 6 już nie (bo średnia dzielników wynosi 2.50, a pierwiastek nieco ponad 2.44).

Jasio jest zainteresowany obliczeniem, ile w danym przedziale znajduje się liczb znaczących. Pomóż mu znaleźć odpowiedź na to pytanie.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą t (t<=100000). W kolejnych liniach podanych jest t przypadków testowych.

Każdy przypadek testowy złożony jest z jednej linii zawierającej parę liczb całkowitych a b, określających dolne i górne ograniczenie przedziału badanego przez Jasia (1<=a<=b<=10⁹).

Wyjście

Dla każdego przypadku testowego, wypisz ile liczb znaczących znajduje się w przedziale [a,b].

Przykład

Wejście:
2
4 6
1 3

Wyjście:
1
0