## Problem Description

Squeaky the Rat found a shiny new array of *N* integers *A*_{1}, *A*_{2}, ..., *A*_{N}

Kraw the Krow is envious of Squeaky the Rat's shiny new array and is now going to ask Squeaky the Rat *M* questions regarding the array to see how well Squeaky the Rat knows his new array.

Squeaky the Rat comes up with a strange function d(*q*). d(*q*) represents the number of indices *j* such that *A*_{j} is divisible by *q*. Then, Squeaky the Rat provides Kraw the Krow with two integers *L*_{i} and *R*_{i} and asks *M* questions of the form:

Evaluate Σ_{q∈V(Li, Ri)} d(*q*)
where V(*L*_{i}, *R*_{i}) is the set of prime numbers {*P*_{i}} where *L*_{i} ≤ *P*_{i} ≤ *R*_{i}.

Kraw the Krow wants to prove to Squeaky the Rat that he knows his new array well. Help him answer Squeaky the Rat's queries.

## Input

The first line of input will contain one integer, *N*.

The next line of input will contain *N* space separated integers *A*_{1}, *A*_{2}, ..., *A*_{N}.

The following line of input will contain one integer, *M*.

The next *M* lines of input will contain two integers each, *L*_{i} and *R*_{i}.

## Output

Output *M* lines. On the *i*th line, output a single integer, the answer to Squeaky's *i*th question.

## Limits

For all subtasks, 1 ≤ *A*_{i} ≤ 10^{7}.

Subtask 1 (32%): 1 ≤ *N, M* ≤ 500. 2 ≤ *L*_{i} ≤ *R*_{i} ≤ 5000.

Subtask 2 (68%): 1 ≤ *N* ≤ 10^{6}. 1 ≤ *M* ≤ 50 000. 2 ≤ *L*_{i} ≤ *R*_{i} ≤ 2 × 10^{9}.

Subtask 3 (0%): Sample Testcases

## Sample Testcase 1

### Input

6
5 5 7 10 14 15
3
2 11
3 12
4 4

### Output

9
7
0