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
import math
from collections import defaultdict,Counter
from itertools import permutations
from collections import deque
 
 
def sin():
	return int(sys.stdin.readline())
 
def array():	
	return list(map(int, sys.stdin.readline().strip().split()))
 
def two():
	return map(int, sys.stdin.readline().strip().split())
 
def multiple():
	return [int(x) for x in sys.stdin.readline().split()]
 
def string():
	return sys.stdin.readline().strip()
 
def sqrt(x):
	low , high = 0 , x
	while low <= high:
		mid = (low + high) // 2
		if mid * mid <= x < (mid+1) * (mid+1):
			return mid
		elif x < mid * mid:
			high = mid - 1
		else:
			low = mid + 1
 
 

n = sin()
arr = array()

new = set(arr)

prime = [0] * (10**7)
seive = [0] * (10**7)

count = defaultdict(int)

for i in arr:
	count[i] += 1

for i in range(2 , (10**7)):
	if not seive[i]:
		for j in range(i , 10**7 , i):
			seive[j] = 1
			prime[i] += count[j]

# print(prime[:10])

for i in range(1,10**7):
	prime[i] += prime[i-1]


# print(prime[:10])

q = sin()
for _ in range(q):
	l,r = multiple()

	print(prime[r] - prime[l-1])
