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 bisect
n=int(input())
arr=list(map(int,input().split(" ")))
arr.sort()
m=int(input())
def solve(n):
  sieve = [True] * (n + 1)
  primes = []
  for i in range(2, n + 1):
      if sieve[i]:
        primes.append(i)
        for j in range(i, n + 1, i):
            sieve[j] = False
  return primes
primes=solve(max(arr))
# print(primes)
d=[0 for i in range(len(primes))]
for i in arr:
  j=0
  while(i!=1 and j<len(primes)):
    if i%primes[j]==0:
      d[j]+=1
    while(i%primes[j]==0):
      i=i//primes[j]
    j+=1
# print(d)
for i in range(1,len(d)):
  d[i]+=d[i-1]
for _ in range(m):
  [a,b]=list(map(int,input().split(" ")))
  k=bisect.bisect_left(primes,a)
  print(d[bisect.bisect_right(primes,b)-1]-(d[k-1] if k else 0))