AlgoLiga 2018

- Wiosna panie sierżancie!, wrzasnęła Zuzia, asystentka pani Marii, do Tomka, technika skanującego kolejne mapy i zdjęcia satelitarne. Oboje są pracownikami pani Marii. Zuzia jak co dzień z samego rana podała już kawę szefowej i teraz ma 4,5 minuty do 12:05 .... To już stały rytuał od ponad 9 lat. Na dworze jest jeszcze śnieg i mróz ale Zuzia dzisiaj wyczuła jakieś inne, niecodzienne, wiosenne?, dziwne zachowanie pani Marii. Jest dzisiaj nie tylko niezwykle miła dla pracowników, odpowiedziała już na jednego e-maila i od rana podśpiewuje i wzdycha pod nosem "Wiosna, wiosna, wiosna ach to Ty..". Coś dziwnego dzieje się z panią Marią!? Dzisiaj przygotowała też łatwe i miłe zadanie, co jest u niej bardzo dziwne i niespotykane. Może pod wpływem coraz dłuższych okresów w ciągu dnia, w których promienie słoneczne wpadają do mrocznego gabinetu szefowej, może spóźnione walentynki a może był to jakiś inny tajemniczy powód, który spowodował, że zimne i twarde jak bryła lodu serce pani Sędziospoj trochę skruszało i odtajało. Tak myśli i czuje Zuzia i dlatego tak właśnie krzyknęła do Tomka. Dlatego, szybko wykorzystaj okazję i zgłoś program-rozwiązanie tego zadania. Jutro, z samego rana pani Maria jak tylko wejdzie do gabinetu i zanim poprosi o kawę, od razu włączy monitor i komputer i na pewno zablokuje dostęp do serwera i do zadań. Wszystko może wrócić do normy, może to był tylko przelotny kaprys pani Marii. Znowu będzie tak samo, jak zawsze od ponad 9 lat zawsze z samego rana o 12:00.

Oto to zadanie: Ile liczb naturalnych z podanego przedziału [s_p, s_k], jest podzielnych przez obie lub jedną z dwóch podanych liczb a i b?

Wejście

Najpierw, w pierwszej linii dwie liczby całkowite 0 < a, b < 2³¹.
Potem nieokreślona ilość par liczb całkowitych 0 < s_p ≤ s_k < 2³¹ (każda para w nowej linii).

Wyjście

Dla każdego podanego przedziału podać w oddzielnej linii wynik.

Przykład

Wejście:
3 5
1 2
1 3
3 5
1 100

Wyjście:
0
1
2
47