Bố Tài Super Cute hôm nay lại cho các con zai yêu một bài toán vui. Bố viết một dãy ~n~ số nguyên dương ~x_1, x_2, ..., x_n~ và đặt ra ~m~ câu hỏi. Với mỗi câu, bố cho hai số nguyên dương ~L, R~ và với từng số nguyên tố ~p~ thuộc đoạn ~[L;R]~, bố muốn tính số lượng bội của ~p~ có trong dãy đã cho, sau đó cộng hết các kết quả lại với nhau. Bạn hãy đóng vai làm con zai yêu của bố Tài super cute để giải quyết bài toán này nhé.

Input

• Dòng đầu tiên chứa số nguyên ~n~ với ~1≤ n ≤ 10^5.~
• Dòng thứ 2 chứa ~n~ số nguyên dương ~x_1, x_2, …, x_n~ với ~2 ≤ x_i ≤ 10^7~
• Dòng thứ 3 chứa số nguyên ~m~ với ~1 ≤ m ≤ 50000~. Mỗi dòng ~i~ trong ~m~ dòng sau chứa 2 số nguyên ngăn cách bởi 1 dấu cách ~L, R~ với ~2 ≤ L ≤ R ≤ 2.10^9~.

Output

• Gồm m dòng, mỗi dòng 1 số nguyên là câu trả lời cho một truy vấn.

Sample input

6
5 5 7 10 14 15
3
2 11
3 12
4 4

Sample output

9
7
0

Giải thích: trong câu hỏi 1, ta thấy có các số nguyên tố ~2,3,5,7,11~ trong đoạn đã cho. Ta tính được lần lượt có: ~2,1,4,2,0~ bội của chúng trong dãy, vì thế tổng cần tìm là ~9~. Tương tự với các câu hỏi khác.

Subtask

• Sub1: 30% test có ~0 < n, m ≤ 2.10^3, 2 ≤ L ≤ R ≤ 10^3.~
• Sub2: 30% test có ~0 < n, m ≤ 2.10^3, 2 ≤ L ≤ R ≤ 10^6.~
• Sub3: 40% test có ràng buộc như đề bài đã mô tả.