Problem description

Jasio wierzy w magię liczb. Wierzy, że wszystkie liczby podzielne przez co najmniej jeden z N magicznych dzielników: D₁, D₂, …, D_N, posiadają magiczną moc – nazwał je ,,magicznymi liczbami’’. Chce poznać ile jest magicznych liczb z przedziału [A;B].

Napisz program, który: wczyta końce przedziału A, B oraz ,,magiczne dzielniki’’, wyznaczy liczbę magicznych liczb w zadanym przedziale, wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne A i B, oddzielone pojedynczym odstępem. Są to końce przedziału, w którym Jasio szuka magicznych liczb. W drugim wierszu znajduje się jedna liczba naturalna N, określająca liczbę magicznych dzielników, które zna Jasio. W trzecim i ostatnim wierszu wejścia znajduje się N parami różnych liczb naturalnych D_i, pooddzielanych pojedynczymi odstępami. Są to magiczne dzielniki Jasia.

Wyjście

Twój program powinien wypisać na wyjście dokładnie jedną liczbę całkowitą – liczbę magicznych liczb Jasia w zadanym przedziale.

Ograniczenia

1 ≤ N ≤ 20, 1 ≤ A ≤ B ≤ 10¹⁸, 1 ≤ D_i ≤ 10¹⁸.

Przykład

8 15
2
2 3

6