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.
# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 1/2/20

"""

import collections
import time
import os
import sys
import bisect
import heapq
from typing import List



N = int(input())
A = [int(x) for x in input().split()]
M = int(input())
Q = []

MAXV = max(A)
p = [True for _ in range(MAXV+1)]
p[0] = p[1] = False
for i in range(2, len(p)):
    if p[i]:
        v = i + i
        while v < len(p):
            p[v] = False
            v += i

primes = [i for i in range(len(p)) if p[i]]
NP = len(primes)

pi = {p: i for i, p in enumerate(primes)}
count = [0 for _ in range(NP)]

for v in A:
    for i, u in enumerate(primes):
        if u > v:
            break
        if v % u == 0:
            count[i] += 1
            while v % u == 0:
                v //= u
    if v > 1:
        count[pi[v]] += 1
        

ft = [0 for _ in range(NP)]

def add(idx, val):
    while idx < NP:
        ft[idx] += val
        idx |= idx + 1


def query_imp(r):
    v = 0
    while r >= 0:
        v += ft[r]
        r = (r & (r+1)) - 1
    return v


def query(l, r):
    return query_imp(r) - query_imp(l-1)


for i, v in  enumerate(count):
    add(i, v)

ans = []
for mi in range(M):
    l, r = map(int, input().split())
    i = bisect.bisect_left(primes, l)
    if i >= NP:
        ans.append(0)
        continue
    if primes[i] < l:
        i += 1
    j = bisect.bisect_right(primes, r)
    ans.append(query(i, j-1))
    

print('\n'.join(map(str, ans)))
