Treść
Dyzio jest chłopcem, który bardzo lubi matematykę. Ostatnio poznał bardzo ciekawe liczby, zwane liczbami pierwszymi. Po lekcji został mu jednak bardzo duży niedosyt. Pani wypisała tylko kilka przykładów takich liczb, a Dyzio chciałby poznać je wszystkie. Postanowiłeś pomóc młodemu matematykowi i uświadomić mu, że liczby pierwsze nie występują tak rzadko, jak mu się wydaje. Napisz program, który dla zadanego przez Dyzia przedziału wyznaczy liczbę liczb pierwszych w nim zawartych.


Wejście
Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20000) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych
W pierwszym i jedynym wierszu zestawu danych znajdują się dwie liczby a i b (2<=a<=b<=10⁶), oddzielone pojedynczą spacją, oznaczające odpowiednio początek i koniec przedziału domkniętego, dla którego program będzie wyznaczał ilość liczb pierwszych.

Wyjście
Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest liczba liczb pierwszych znajdujących się w przedziale domkniętym [a,b].


Przykład

dane wejściowe:
2
6 19
12 50

wynik:
5
10