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 math
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
m = int(input())
d = defaultdict(int)


def prfact(n, d):
    vis = True
    while n % 2 == 0:
        if vis:
            d[2] += 1
            vis = False
        n /= 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        v = True
        while n % i == 0:
            if v:
                d[i] += 1
                v = False
            n /= i
    if n > 2:
        d[n] += 1


def ceilSearch(arr, low, high, x):
    if x <= arr[low]:
        return low
    if x > arr[high]:
        return -1
    mid = (low + high) // 2
    if arr[mid] == x:
        return mid
    elif arr[mid] < x:
        if mid + 1 <= high and x <= arr[mid + 1]:
            return mid + 1
        else:
            return ceilSearch(arr, mid + 1, high, x)
    else:
        if mid - 1 >= low and x > arr[mid - 1]:
            return mid
        else:
            return ceilSearch(arr, low, mid - 1, x)


def floorSearch(arr, low, high, x):
    if (low > high):
        return -1
    if (x >= arr[high]):
        return high
    mid = int((low + high) // 2)
    if (arr[mid] == x):
        return mid
    if (mid > 0 and arr[mid - 1] <= x
        and x < arr[mid]):
        return mid - 1
    if (x < arr[mid]):
        return floorSearch(arr, low, mid - 1, x)
    return floorSearch(arr, mid + 1, high, x)


for e in a:
    prfact(e, d)
print(d)
p = []
q = []
for elem in d:
    p.append([elem, d[elem]])
    q.append(elem)
p.sort()
q.sort()
q.insert(0, 0)
x = p[0][0]
y = p[len(p) - 1][0]
s = 0
for i in range(1, len(p)):
    p[i][1] += p[i - 1][1]
p.insert(0, [0, 0])
print(p)
print(q)
for query in range(m):
    l, r = map(int, input().split())
    if l == r:
        print(0)
    else:
        up, dn = None, None
        j, k = True, True
        if l < x:
            l = x
            j = False
            dn = q.index(l)
        if r > y:
            r = y
            k = False
            up = q.index(r)
        if j:
            dn = ceilSearch(q, 0, len(q) - 1, l)
        if k:
            up = floorSearch(q, 0, len(q) - 1, r)
        if dn > up:
            print(0)
        else:
            print(p[up][1] - p[dn - 1][1])