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, threading
import math
from os import path
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
import heapq
 
 
def readInts():
    x = list(map(int, (sys.stdin.readline().rstrip().split())))
    return x[0] if len(x) == 1 else x
 
 
def readList(type=int):
    x = sys.stdin.readline()
    x = list(map(type, x.rstrip('\n\r').split()))
    return x
 
 
def readStr():
    x = sys.stdin.readline().rstrip('\r\n')
    return x
 
 
write = sys.stdout.write
read = sys.stdin.readline
 
 
MAXN = 1123456


class mydict:
    def __init__(self, func):
        self.random = randint(0, 1 << 32)
        self.default = func
        self.dict = {}
 
    def __getitem__(self, key):
        mykey = self.random ^ key
        if mykey not in self.dict:
            self.dict[mykey] = self.default()
        return self.dict[mykey]
 
    def get(self, key, default):
        mykey = self.random ^ key
        if mykey not in self.dict:
            return default
        return self.dict[mykey]
 
    def __setitem__(self, key, item):
        mykey = self.random ^ key
        self.dict[mykey] = item
 
    def getkeys(self):
        return [self.random ^ i for i in self.dict]
 
    def __str__(self):
        return f'{[(self.random ^ i, self.dict[i]) for i in self.dict]}'

 
def lcm(a, b):
    return (a*b)//(math.gcd(a,b))
 
 
def mod(n):
    return n%(1000000000 + 7) 


def primeFactors(n):
    
    mp = defaultdict(lambda: 0)

    while n % 2 == 0:
        mp[2] += 1
        n = n // 2

    for i in range(3,int(math.sqrt(n))+1,2):

        while n % i== 0:
            mp[i] += 1
            n = n // i
             
    if n > 2:
        mp[n] += 1

    return mp

def upper_bound(a, num):
    l = 0
    r = len(a)-1
    ans = -1
    while l <= r:
        mid = (l+r)//2
        if a[mid] >= num:
            ans = mid
            r = mid-1
        else:
            l = mid+1

    return ans

def lower_bound(a, num):
    l = 0
    r = len(a)-1
    ans = -1
    while l <= r:
        mid = (l+r)//2
        if a[mid] <= num:
            ans = mid 
            l = mid+1
        else:
            r = mid-1

    return ans


def solve(t):
    # print(f'Case #{t}: ', end = '')
    n = readInts()
    ar = readList()
    gmp = defaultdict(lambda: 0)
    for num in ar:
        mp = primeFactors(num)
        for fac in mp:
            gmp[fac] += 1

    kar = sorted(list(gmp.keys()))
    indmp = defaultdict(lambda: None)
    for i, num in enumerate(kar):
        indmp[num] = i

    pref = [0]
    s = 0
    for num in kar:
        s += gmp[num]
        pref.append(s)

    q = readInts()
    # print(gmp)
    # print(indmp)
    # print(pref)
    for _ in range(q):
        l, r = readInts()
        ui = upper_bound(kar, l)
        li = lower_bound(kar, l)
        if ui != -1:
            l = indmp[kar[ui]]
        elif li != -1:
            l = indmp[kar[li]]
        else:
            print(0)
            continue

        ui = upper_bound(kar, r)
        li = lower_bound(kar, r)
        if li != -1:
            r = indmp[kar[li]]
        elif ui != -1:
            r = indmp[kar[ui]]
        else:
            print(0)
            continue

        # print(l, r)
        print(pref[r+1] - pref[l])


def main():
    t = 1
    if path.exists("F:/Comp Programming/input.txt"):
        sys.stdin = open("F:/Comp Programming/input.txt", 'r')
        sys.stdout = open("F:/Comp Programming/output1.txt", 'w')
    # sys.setrecursionlimit(10**6) 
    # t = readInts()
    for i in range(t):
        solve(i+1)
 
 
if __name__ == '__main__':
    main()  