Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PZPI3 - Liczby znaczące

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<=109).

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

Dodane przez:adrian
Data dodania:2005-05-21
Limit czasu wykonania programu:3.124s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:I Pomorskie Zawody w Programowaniu Indywidualnym - fina³
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.