Bear và các số nguyên tố

Cho dãy số nguyên $x_1,x_2,\dots ,x_n$ (các số không nhất thiết phân biệt).

Với mỗi số nguyên tố $p$, đặt $f(p)$ là số lượng chỉ số $k$ sao cho $x_k$ chia hết cho $p$.

Bạn nhận được $m$ truy vấn, truy vấn thứ $i$ gồm hai số nguyên $l_i$ và $r_i$. Đáp án của truy vấn là

$$\sum _{p\in S(l_i,r_i)}f(p)$$

trong đó $S(l,r)$ là tập tất cả các số nguyên tố nằm trong đoạn $[l,r]$ (tính cả hai đầu mút).

Lưu ý rằng $r_i$ có thể lớn hơn mọi giá trị $x_k$; khi đó mọi số nguyên tố $p$ lớn hơn $max{x}_k$ đều cho $f(p)=0$ và không đóng góp gì vào tổng.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\dots ,x_n$.
• Dòng thứ ba chứa số nguyên $m$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i$ và $r_i$.

Dữ liệu ra

In ra $m$ dòng, dòng thứ $i$ là đáp án của truy vấn thứ $i$, theo đúng thứ tự trong dữ liệu vào.

Ràng buộc

• $1\le n\le {10}^6$
• $2\le x_k\le {10}^7$
• $1\le m\le 50000$
• $2\le l_i\le r_i\le 2·{10}^9$

Ví dụ