Đàn kiến

Một đàn kiến gồm $n$ con xếp thành một hàng. Con kiến thứ $i$ có sức mạnh $s_i$.

Với một đoạn $[l,r]$, xét tất cả các con kiến có chỉ số từ $l$ đến $r$. Một con kiến $i$ (với $l\le i\le r$) được giải thoát nếu $s_i$ là ước của $s_j$ với mọi $j$ thỏa $l\le j\le r$ (tức $s_i$ chia hết tất cả sức mạnh trong đoạn). Những con kiến còn lại (không được giải thoát) sẽ bị ăn thịt.

Cho $t$ truy vấn, mỗi truy vấn là một đoạn $[l,r]$. Với mỗi truy vấn, hãy đếm xem có bao nhiêu con kiến trong đoạn đó bị ăn thịt.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số lượng kiến.
• Dòng thứ hai chứa $n$ số nguyên $s_1,s_2,\dots ,s_n$ — sức mạnh của các con kiến.
• Dòng thứ ba chứa số nguyên $t$ — số lượng truy vấn.
• $t$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l$ và $r$ mô tả một truy vấn.

Dữ liệu ra

In ra $t$ dòng, dòng thứ $i$ là số con kiến bị ăn thịt trong truy vấn thứ $i$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le s_i\le {10}^9$
• $1\le t\le {10}^5$
• $1\le l\le r\le n$

Ví dụ