Đàn kiến (Ant Colony)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Có $N$ con kiến đứng thành một hàng. Kiến thứ $i$ có sức mạnh $s_i$. Với một đoạn $[l,r]$, mọi cặp kiến trong đoạn đều đấu với nhau. Khi kiến $i$ đấu với kiến $j$, kiến $i$ nhận một điểm nếu $s_i$ chia hết $s_j$.

Một con kiến được thả nếu nó nhận điểm trong mọi trận mà nó tham gia, tức đạt đúng $r-l$ điểm. Những con còn lại bị ăn.

Với mỗi truy vấn $[l,r]$, hãy cho biết có bao nhiêu con kiến bị ăn.

Input

Dòng đầu chứa $N$.

Dòng thứ hai chứa $s_1,s_2,\ldots,s_N$.

Dòng thứ ba chứa $Q$.

$Q$ dòng tiếp theo, mỗi dòng chứa $l,r$.

Output

Với mỗi truy vấn, in số kiến bị ăn.

Subtask

• 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$.

Ví dụ

Input

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

Output

4
4
1
1

Giải thích

Trong truy vấn $[1,5]$, GCD của cả đoạn là $1$ và chỉ một kiến có sức mạnh $1$ được thả, vì vậy $4$ kiến bị ăn.