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,os,io
from math import log, gcd
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right


# Iterative Python3 program 
# to compute modular power 

# Iterative Function to calculate 
# (x^y)%p in O(log y) 

import math 
  
# A function to print all prime factors of  
# a given number n 
def primeFactors(n): 
      
    # Print the number of two's that divide n 
    l = []
    while n % 2 == 0: 
        l.append(2)
        n = n / 2
          
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3,int(math.sqrt(n))+1,2): 
          
        # while i divides n , print i ad divide n 
        while n % i== 0: 
            l.append(int(i))
            n = n / i 
              
    # Condition if n is a prime 
    # number greater than 2 
    if n > 2: 
        l.append(n)
    return list(set(l))
    
def power(x, y, p) : 
	res = 1
	x = x % p 
	if (x == 0) : 
		return 0
	while (y > 0) : 
		if ((y & 1) == 1) : 
			res = (res * x) % p 
		y = y >> 1	 # y = y/2 
		x = (x * x) % p 		
	return res 


def si():
    return input()

# input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def prefix_sum(arr):
    r = [0] * (len(arr)+1)
    for i, el in enumerate(arr):
        r[i+1] = r[i] + el
    return r

def divideCeil(n,x):
    if (n%x==0):
        return n//x
    return n//x+1

def ii():
    return int(input())

def li():
    return list(map(int,input().split()))



# t = int(input())
t = 1
for _ in range(t):
    n = ii()
    l = li()
    dic = defaultdict(lambda:0)
    dicmap = defaultdict(lambda:0)
    for i in l:
        x = primeFactors(i)
        for j in x:
            dic[j]+=1
    arr = []
    x = list(dic.keys())
    x.sort()
    arr = []
    ind = 0
    pre = []
    for i in x:
        if (pre==[]):
            pre.append(dic[i])
        else:
            pre.append(pre[-1] + dic[i])
        arr.append(dic[i])
        dicmap[i] = ind
        ind+=1
    

    m = ii()
    ans = []
    # print(dicmap)
    for _ in range(m):
        ll,rr = li()
        m1 = bisect_left(x,ll)
        m2 = bisect_right(x,rr)
        if (m1==0):
            ans.append(pre[m2-1])
        else:
            ans.append(pre[m2-1]-pre[m1-1])
        # print(m1,m2)
    for i in ans:
        print(i)
    # print(x)
    # print(pre)
    # print(ans)




    # x.sort()
    # ind = 0
    # x1 = []
    # for i in x:
    #     dicmap[i]=ind 
    #     arr.append(dic[i])
    #     ind+=1
    # m = ii()
    
    # pre = prefix_sum(arr)
    # for i in range(m):
    #     ll,rr = li()
    #     m1 = dicmap[bisect_left(x,ll)]
    #     m2 = dicmap[bisect_right(x,rr)]
    #     print(pre[m2]-pre[m1])
    # print("pre",pre)
    # print("arr",arr)
    # print(dicmap)




