#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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*and

_{i}*R*and asks

_{i}*M*questions of the form:

_{q∈V(Li, Ri)}d(

*q*)

where V(*L _{i}*,

*R*) is the set of prime numbers {

_{i}*P*} where

_{i}*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*≤ 5000.

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

*R*≤ 2 × 10

_{i}^{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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 32 | 30 | 2s | 256MB | Minimum |

2 | 68 | 40 | 2s | 256MB | Minimum |

3 | 0 | 1 | 2s | 256MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o primecount -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512