Recently, the bear started studying data structures and faced the following problem.

You are given a sequence of integers *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*n*</sub> of length *n* and *m* queries, each of them is characterized by two integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>. Let's introduce *f*(*p*) to represent the number of such indexes *k*, that *x*<sub class="lower-index">*k*</sub> is divisible by *p*. The answer to the query *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> is the sum: <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/5e448f6c1a0e40843cecdbbeb95970464626032f.png" style="max-width: 100.0%;max-height: 100.0%;"/>, where *S*(*l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>) is a set of prime numbers from segment [*l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>] (both borders are included in the segment).

Help the bear cope with the problem.
The first line contains integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">6</sup>). The second line contains *n* integers *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*n*</sub> (2 ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">7</sup>). The numbers are not necessarily distinct.

The third line contains integer *m* (1 ≤ *m* ≤ 50000). Each of the following *m* lines contains a pair of space-separated integers, *l*<sub class="lower-index">*i*</sub> and *r*<sub class="lower-index">*i*</sub> (2 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ 2·10<sup class="upper-index">9</sup>) — the numbers that characterize the current query.
import sys
from bisect import bisect_left,bisect_right
from collections import defaultdict as dd
from collections import deque, Counter
from heapq import heappop,heappush,heapify,merge
from itertools import permutations, accumulate, product
from math import gcd,sqrt,ceil
toBin=lambda x:bin(x).replace("0b","")
I=lambda:map(int,input().split())
inf=float("inf");DIRS=[[1,0],[-1,0],[0,1],[0,-1]];CHARS="abcdefghijklmnopqrstuvwxyz";MOD=10**9+7
###### Fill out N to calculate combinations#####################
# N=300010;fac=[1]*N;invfac=[1]*N
# for i in range(2,N):fac[i]=fac[i-1]*i%MOD
# invfac[N-1]=pow(fac[N-1],MOD-2,MOD)
# for i in range(N-1)[::-1]:invfac[i]=invfac[i+1]*(i+1)%MOD
# def c(i,j):return 0 if i<j else fac[i]*invfac[j]*invfac[i-j]
###############################################################
input=sys.stdin.readline

class UnionFind:
    def __init__(self,n):self.p=list(range(n));self.rank=[0]*n
    def find(self,x):
        if x!=self.p[x]:self.p[x]=self.find(self.p[x])
        return self.p[x]
    def union(self,x, y):
        px,py=self.find(x),self.find(y)
        if px==py:return 0
        self.p[py]=px
        self.rank[px]+=self.rank[py]
        return 1

from types import GeneratorType
def cache(f,queue=[]):
    def wrappedfunc(*args,**kwargs):
        if queue:return f(*args, **kwargs)
        else:
            to = f(*args,**kwargs)
            while True:
                if isinstance(to,GeneratorType):queue.append(to);to = next(to)
                else:
                    if not queue:break
                    queue.pop()
                    if not queue:break
                    to=queue[-1].send(to)
            return to
    return wrappedfunc

def query(x,y):
    print("?",x,y,flush=True)
    return int(input())


# Sieve Template - returning a list of primes<n
def sieve(x):
    primes=[True for i in range(x+1)];res=[];i=2
    while i*i<=x:
        if primes[i]:
            for j in range(i*i,x+1,i):primes[j]=False
        i+=1
    for i in range(2,x+1):
        if primes[i]:res.append(i)
    return res

# DP,BS,Greedy,Graph,Contribution,IE,Game,Reverse simulation
def main():
    # for each xi, get prime factors and increment its frequency.
    # calc accum sum. for each query. get the range sum. (pre 20m)
    MAXN=10**7+1;spf=[0 for _ in range(MAXN)];count=[0]*(MAXN)
    def sieve0():
        spf[1]=1
        for i in range(2,MAXN):spf[i]=i
        for i in range(4,MAXN,2):spf[i]=2
        for i in range(3,ceil(sqrt(MAXN))):
            if spf[i]==i:
                for j in range(i*i,MAXN,i):
                    if spf[j]==j:spf[j]=i
    def getfactorization(x):
        v=set()
        while x!=1:
            p=spf[x]
            if p==spf[x] and p not in v:count[p]+=1;v.add(p)
            x//=spf[x]
    sieve0()
    n=int(input());A=list(I());m=int(input())
    for a in A:getfactorization(a)
    for i in range(1,MAXN):count[i]+=count[i-1]
    # print(count[:11],spf[:11])
    for _ in range(m):
        l,r=I();l=min(l,10**7);r=min(r,10**7)
        print(count[r]-count[l-1])
###### Comment this out for Python 3 + imports at the top #####
if __name__ == "__main__":
    main()

###### Uncomment this for Python 3 (for deep recursion) ######
# import sys
# import threading
# sys.setrecursionlimit(500000);I=lambda:map(int,input().split());input=sys.stdin.readline
# threading.stack_size(10**8)
# t = threading.Thread(target=main)
# t.start()
# t.join()