import itertools
import math
from functools import reduce

N = []

for _ in range(int(input().strip())):
    N.append(int(input().strip()))
N = list(set(N))
N.sort()

Nref = N.copy()
for i in N:
    for b in N:
        if i % b == 0 and i != b:
            Nref.remove(i)
            break


def val(i, L, R):
    if i > R:
        return 0
    low = L//i
    high = R//i
    if L % i == 0:
        low -= 1
    return high - low


#MAIN CODE
for _ in range(int(input().strip())):
    ans = 0
    L, R = map(int, input().strip().split())
    
    for i in range(1, len(Nref)+1):
        for j in itertools.combinations(Nref, i):
            lcm = reduce(math.lcm, j)
            ans += (-1)**(i-1)*val(lcm, L, R)
    print(ans)