## Problem Description

Squeaky the Rat found a shiny new array of N integers A1, A2, ..., AN

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 Aj is divisible by q. Then, Squeaky the Rat provides Kraw the Krow with two integers Li and Ri and asks M questions of the form:

Evaluate Σq∈V(Li, Ri) d(q)

where V(Li, Ri) is the set of prime numbers {Pi} where LiPiRi.

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 A1, A2, ..., AN.

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

The next M lines of input will contain two integers each, Li and Ri.

## Output

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

## Limits

For all subtasks, 1 ≤ Ai ≤ 107.

Subtask 1 (32%): 1 ≤ N, M ≤ 500. 2 ≤ LiRi ≤ 5000.

Subtask 2 (68%): 1 ≤ N ≤ 106. 1 ≤ M ≤ 50 000. 2 ≤ LiRi ≤ 2 × 109.

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

```9
7
0```