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
#import threading
#sys.setrecursionlimit(10**8)
#threading.stack_size(10**8)
input = sys.stdin.readline

############ ---- Input Functions ---- ############
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))
############ ---- Input Functions ---- ############

def Bear_and_Prime_Numbers():
    n = inp()
    sequence = inlt()

    max_num = max(sequence)
    frequency_list = [0]*max_num

    for num in sequence:
        frequency_list[num-1] += 1
    

    divisor_count = [1]*max_num
    
    for i in range(2,max_num+1):
        if divisor_count[i-1] >= 2:
            divisor_count[i-1] += 1
            continue

        current_num = i 
        while current_num <= max_num:
            divisor_count[current_num-1] += 1
            current_num += i 
    

    prefix_sum = []
    running_sum = 0 

    for num in range(1,max_num+1):
        if divisor_count[num-1] == 2:

            current_num = num
            current_sum = 0 

            while current_num <= max_num:
                current_sum += frequency_list[current_num-1]
                current_num += num 
            
            running_sum += current_sum
            prefix_sum.append(running_sum)

        else:
            prefix_sum.append(running_sum)
        
    m = inp()

    outputStr = ''
    for _ in range(m):
        l,r = invr()

        if r > max_num:
            r = max_num
        
        outputStr += str(prefix_sum[r-1] - prefix_sum[l-2]) + '\n'
    
    outputStr = outputStr.strip()
    print(outputStr)

    return



Bear_and_Prime_Numbers()