AlgoLiga 2018

- Jeszcze się tam żagiel bieli, chłopców, którzy odpłynęli..."-  cichutko i smętnie, mocno przy tym fałszując, podśpiewuje sobie pod nosem pani Maria Sędziospoj i tak naprawdę nikt nie wie dlaczego. Możliwe, że tak naprawdę pani Profesor wspomina, coroczną wakacyjną pracę na obozach żeglarskich i wszystkich adeptów żeglarstwa, którzy "wypłynęli" z jej rąk. W każdym razie pani Maria znowu przygotowała swoje wcześniejsze, dobrze znane, lekko tylko zmienione zadanie.

Oto to zadanie: Ile liczb naturalnych z podanego przedziału [s_p, s_k], jest podzielnych przez co najmniej jedną z trzech podanych liczb a, b lub c?

Wejście

Najpierw, w pierwszej linii trzy liczby całkowite 0 < a, b, c < 2³¹.
Potem nieokreślona ilość zapytań, par liczb całkowitych 0 < s_p ≤ s_k < 2³¹ (każda para w nowej linii), które określają początek i koniec przedziału.

Wyjście

Dla każdego podanego przedziału podać w oddzielnej linii wynik, liczbę będącą odpowiedzią na pytanie.

Przykład

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

Wyjście:
0
1
2
55