Ant Colony

Source: Codeforces

Version: Phuoc Hung OJ Extended

There are $N$ ants in a row. Ant $i$ has strength $s_i$. For a query segment $[l,r]$, every pair of ants in the segment fights. Ant $i$ receives one point against ant $j$ if $s_i$ divides $s_j$.

An ant is freed only if it scores a point in every fight it participates in, i.e. exactly $r-l$ points. All other ants are eaten.

For each query, print the number of ants that are eaten.

Input

The first line contains $N$.

The second line contains $s_1,s_2,\ldots,s_N$.

The third line contains $Q$.

Each of the next $Q$ lines contains $l,r$.

Output

Print the number of eaten ants for every query.

Subtasks

• Subtask 1 — 20%: $1\le N,Q\le 50$, $1\le s_i\le 10^4$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$, $1\le s_i\le 10^9$.
• Subtask 3 — 50%: $1\le N,Q\le 10^5$, $1\le s_i\le 10^9$.

Examples

Input

5
1 3 2 4 2
4
1 5
2 5
3 5
4 5

Output

4
4
1
1

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.