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

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 seive(n): 
        primes = [False, False] + [True for i in range(const+2)]

        for i in range(2, const+2):
            if primes[i]: 
                for j in range(i+i, const+2, i): 
                    primes[j] = False

        return primes

    
    n = ii()
    a = li()
    k = ii()
    query = [list(map(int,input().split())) for i in range(k)]
    store = [0 for i in range(const+2)]
    d = [0 for i in range(const+2)]

    const = 10**7
    for ai in a: 
        d[ai] += 1

    primes = seive(const+2)

    for i in range(const+2): 
        if primes[i]: 
            for j in range(i, const+2, i): 
                store[i] += d[j]

    for i in range(1, const+2):
        store[i] += store[i-1]

    for l,m in query: 
        if l > const+1: 
            l = const+1
        if m > const+1:
            m = const+1

        s = store[m] - store[l-1]
        p(str(s))


    

    





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