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.

# Version 20.0
import os, sys, math, itertools
from collections import deque, defaultdict, OrderedDict, Counter
from bisect import bisect, bisect_left, bisect_right, insort
from heapq import heapify, heappush, heappop, nsmallest, nlargest, heapreplace, heappushpop

ii = lambda : int(input())
si = lambda : input()               
mi = lambda : map(int,input().strip().split(" "))
msi = lambda : map(str,input().strip().split(" ")) 
li = lambda : list(mi())
lsi = lambda : list(msi())
out = []
export = lambda : print('\n'.join(map(str, out)), end='')
p = lambda x : out.append(x)
pp = lambda array : p(' '.join(map(str,array)))

offline = True

L = lambda string : hq.L(string) if offline else False
LT = lambda tc, custom, string : hq.LT(tc, custom, string) if offline else False

def main() -> None:
    # 2023-09-28 18:59:18
    
    def sieve( n : int) -> list:
        isPrime = [True for i in range(n+1)]
        isPrime[0] = isPrime[1] = False
        for i in range(4,n+1,2): isPrime[i] = False
        for i in range(3,n+1,2):
            if i*i <= n and isPrime[i]:
                for j in range(i*i,n+1,i): isPrime[j] = False
        return [idx for idx,i in enumerate(isPrime) if i==True]


    length = ii()
    global l
    l = li()
    times = ii()
    store = []
    m = float('-inf')
    for _ in range(times):
        a,b = mi()
        store.append([a,b])
        m = max(m,max([a,b]))
    

    all_primes = sieve(m)
    from functools import lru_cache
    @lru_cache
    def get_primes(n):
        cnt = 0
        for i in l:
            if i%n == 0:
                cnt+=1
        return cnt


    for s in store:
        temp = 0
        for a in all_primes:
            if s[0] <= a and s[1] >= a:
                temp += get_primes(a)
                #L([a,temp])

        print(f"{temp}",end="\n")





try: exec('from hq import *\nexec(cc)')
except (FileNotFoundError, ModuleNotFoundError): offline >> 1; main(); export()
	 		 	   	    		 	 	  		    			