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.

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