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)

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii > vii;
typedef vector<vii > vvii;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
 
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define MEM(a,b) memset(a,(b),sizeof(a))
#define pr(a) cout<<#a<<" = "<<(a)<<endl
#define cin(n) int (n); scanf("%d", &(n))
#define cin2(n,m) int (n),(m); scanf("%d%d",&(n),&(m))
#define cout(n) printf("%d\n",n);
#define cinll(n) ll (n); scanf("%lld", &(n))
#define cinll2(n,m) ll (n),(m); scanf("%lld%lld",&(n),&(m))
#define coutll(n) printf("%lld\n",n);
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define loop(x,a,b) for(int (x) = (a);(x)<(b);(x)++)
#define rep(x,n)   for(int (x)=0;(x)<(n);(x)++)
#define tr(c,it) for(typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define prc(a) tr(a, it) cout<<*(it)<<" "; cout<<endl
#define pra(a,n) for(int i=0; i<(n); i++) printf("%d ",((a)[i])); printf("\n") 
#define present(c,x) ((c).find(x) != (c).end()) 
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define ain(a,n) int ((a)[(n)]); for(int i=0; i<(n); i++) scanf("%d",&((a)[i])) 
#define vin(a,n) vector<int> (a); (a).resize((n)); for(int i=0; i<(n); i++) scanf("%d",&((a)[i])) 
#define MOD 1000000007

pair<ll,int> mask[1<<18];

int main(){
	cin(n);
	ain(ip,n);
	int temp = 0;
	ll temp1 = 1;
	loop(i,1,1<<n){
		temp = __builtin_popcount(i);
		temp1 = 1;
		rep(j,n){
			if((1<<j)&i){
				ll temp2 = (__gcd(temp1,ll(ip[j])));
				temp1 = (temp1*ll(ip[j]))/(temp2);
			}
			//cout<<temp1<<" "<<i<<" "<<ip[j]<<endl;
		}
		//cout << i <<" "<<temp1<<" " <<temp<<endl;
		mask[i].X = temp1;
		mask[i].Y = (temp%2)?0:1; // 0 for + and 1 for -
	}
	cin(q);
	while(q--){
		ll result = 0;
		cinll2(a,b);
		loop(i,1,1<<n){
			ll yo = b/mask[i].X;
			yo -= (a-1)/mask[i].X;
			if(mask[i].Y)
				yo = -yo;
			result += yo;
		}
		coutll(result);
	}
	return 0;
}