Problem description

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

W pierwszym wierszu podana jest liczba Q zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem: W pierwszym i jedynym wierszu zestawu danych znajdują się dwie liczby A_i i B_i 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_i,B_i].

Ograniczenia

1 ≤ Q ≤ 20 000, 1 ≤ A_i ≤ B_i ≤ 1 000 000.

Przykład

2
6 19
12 50

5
10