POLSKI SPOJ

Z danego przedział‚u [a..b] naleźy wypisać‡ ile jest liczb naturalnych dodatnich, które nie dzielą… się™ przez źadną… liczbę™ z multizbioru A = {a₁, a₂, ..., a_n}.

Wejś›cie

W pierwszym wierszu jedna liczba n okreś›lająca ilość‡ elementów multizbioru A (n ≤ 10000).

W drugim wierszu n liczb multizbioru. Kaźda z nich mieści się™ w przedziale [1..10⁶].

W trzecim wierszu jedna liczba q oznaczają…ca liczbę™ zapytań„ (q ≤ 10000).

Kaźde zapytanie jest reprezentowane przez dwie liczby a i b określają…ce przedział w postaci [a..b], gdzie a ≤ b oraz a, b ∈ [1..10⁶].

Wyjś›cie

Dla każdego zapytania wypisz liczbę™ liczb niepodzielnych przez żadną… liczbę z multizbioru A.

Przykł‚ad

Wejście:
3
2 3 4
2
1 10
10 20

Wyjś›cie:
3
4