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.
prime=[2,3,5,7,11,13]
dic={}

def create_list(n):
    global prime
    for x in range(prime[-1]+2,n+1,2):
        notPrime=False
        hold=int(x**0.5)+1
        for j in prime:
            if j>hold:
                break
            if x%j==0:
                notPrime=True
                break
        if notPrime==False:
            prime.append(x)
    #print(len(prime))

def isPrime(n):
    if n<=1:return False
    if n==2 or n==3 or n==5:return True
    if (n&1)==0:return False
    hold = int(n**0.5)+2
    for i in range(3,hold,2):
        if n%i==0:
            return False
    return True

def get_index(x):
    if x==2:
        return 1
    if x%2==0:
        x-=1
    while isPrime(x)==False:
        x-=2
    return dic[x]

def main():
    mode="filee"
    if mode=="file":f=open("test.txt","r")
    #f.readline()
    #input()
    get = lambda :[int(x) for x in (f.readline() if mode=="file" else input()).split()]
    [n]=get()
    a=get()
    create_list(3500)
    i=1
    leng=len(prime)
    while i<leng:
        dic[prime[i-1]]=0
        i+=1
    i=0
    alen = len(a)
    while i<alen:
        j=0
        hold = a[i]**0.5+2
        while prime[j]<=hold:
            if a[i]%prime[j]==0:
                while a[i]%prime[j]==0:
                    a[i]//=prime[j]
                dic[prime[j]]+=1
            j+=1
        if isPrime(a[i])==True:
            if a[i] in prime:
                dic[a[i]]+=1
            else:
                prime.append(a[i])
                dic[a[i]]=1
        i+=1
    tt = sorted(dic.items(), key=lambda x: x[0])
    leng = len(tt)
    s=[0]*(leng)
    i=1
    while i<leng:
        s[i]=s[i-1]+tt[i-1][1]
        i+=1
    i=0
    while i<leng:
        dic[tt[i][0]]=i+1
        i+=1
    [m]=get()
    for z in range(m):
        [l,r] = get()
        if l>10**7:l=10**7
        if r>10**7:r=10**7
        x=get_index(l)
        y=get_index(r)
        if x==y and l!=x:
            print(0)
            continue
        print(s[y]-s[x-1])

    if mode=="file":f.close()


if __name__=="__main__":
    main()
