Số 0 tận cùng

Chú gấu Tommy là một chú gấu rất dễ thương. Một ngày nọ chú đến trường và được thầy dạy về những con số nguyên tố. Chú và các bạn vô cùng thích thú và lao vào tìm hiểu chúng. Thế nhưng, càng tìm hiểu sâu chú lại càng gặp phải những bài toán khó về số nguyên tố. Hôm nay thầy giao cho cả lớp một bài toán khó và yêu cầu cả lớp ai làm nhanh nhất sẽ được thầy cho bánh. Vì thế, để có bánh ăn, Tommy phải giải bài toán nhanh nhất có thể. Bài toán như sau:

Cho dãy $n$ số nguyên dương $x_1,x_2,\dots ,x_n$ và $m$ truy vấn, mỗi truy vấn được cho bởi hai số nguyên $l_i,r_i$. Cho một hàm $f(p)$ trả về số lượng các số $x_k$ ($1\le k\le n$) là bội của $p$ (các số $x_k$ bằng nhau ở các vị trí khác nhau được đếm riêng). Câu trả lời cho truy vấn $l_i,r_i$ là tổng

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

trong đó $S(l_i,r_i)$ là tập các số nguyên tố trong đoạn $[l_i,r_i]$ (tính cả hai đầu mút). Nếu đoạn không chứa số nguyên tố nào thì câu trả lời là $0$.

Bạn hãy giúp chú gấu Tommy giải bài toán này nhé!

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ $(1\le n\le {10}^5)$.
• Dòng thứ hai chứa $n$ số nguyên dương $x_1,x_2,\dots ,x_n$ $(2\le x_i\le {10}^7)$.
• Dòng thứ ba chứa số nguyên $m$ $(1\le m\le 50000)$.
• Mỗi dòng thứ $i$ trong $m$ dòng tiếp theo chứa hai số nguyên $l_i,r_i$ ngăn cách bởi một dấu cách $(2\le l_i\le r_i\le 2·{10}^9)$.

Dữ liệu ra

Gồm $m$ dòng, mỗi dòng ghi một số nguyên là câu trả lời cho một truy vấn, theo thứ tự trong dữ liệu vào.

Ràng buộc

• $1\le n\le {10}^5$.
• $2\le x_i\le {10}^7$.
• $1\le m\le 50000$.
• $2\le l_i\le r_i\le 2·{10}^9$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($30\%$ số test): $n,m\le 2·{10}^3$, $2\le l_i\le r_i\le {10}^3$.
• Subtask 2 ($30\%$ số test): $n,m\le 2·{10}^3$, $2\le l_i\le r_i\le {10}^6$.
• Subtask 3 ($40\%$ số test): không có ràng buộc gì thêm.

Ví dụ