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


if __name__ == "__main__":
    n = int(input())
    x = [int(i) for i in input().split()]
    m = int(input())

    q = []
    prange = [0,0]

    for i in range(m):
        l_str, r_str = input().split()
        l, r = int(l_str), int(r_str)
        if l < prange[0]:
            prange[0] = l
        if r > prange[1]:
            prange[1] = r
        q.append((l, r))

    def get_primes(a,b):
        """ Returns  a list of primes < n """
        sieve = [True] * (b//2)
        for i in range(3, int(b**0.5)+1, 2):
            if sieve[i//2]:
                sieve[i*i//2::i] = [False] * ((b-i*i-1)//(2*i)+1)
        o = [2] + [2*i+1 for i in range(1,b//2) if sieve[i]]
        i = bisect.bisect_left(o, a)
        return o[i:]

    mi, ma = min(x), max(x)
    if prange[1] > ma:
        prange[1] = ma

    primes = get_primes(prange[0], prange[1]+1)

    def solve(x, mi, ma, l, r):
        count = 0
        if r > ma:
            r = ma
        a = bisect.bisect_left(primes, l)
        b = bisect.bisect_right(primes, r)
        for pi in range(a, b):
            p = primes[pi]
            count += sum(1 for n in x if n % p == 0)

        return count


    for l, r in q:
        got = solve(x, mi, ma, l, r)
        print(got)


import unittest

class TestFoo(unittest.TestCase):
    def test_world(self):
        n = [5, 5, 7, 10, 14, 15]

        got = solve(n, 2, 11)
        self.assertEqual(got, 9)

        got = solve(n, 3, 12)
        self.assertEqual(got, 7)

        got = solve(n, 4, 4)
        self.assertEqual(got, 0)

        got = get_max_s('bearaabearc')
        self.assertEqual(got, 20)

