{"code":"tommy004","name":"Chú gấu Tommy và các bạn","description":"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à\r\nđượ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\r\ntì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\r\nkhó 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\r\nai 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\r\ntoán nhanh nhất có thể. Bài toán như sau:\r\n\r\nCho dãy $n$ số nguyên dương $x_1, x_2, ..., x_n$ và $m$ truy vấn, mỗi truy vấn được cho\r\nbởi 2 số nguyên $l_i, r_i$. Cho một hàm f(p) trả về số lượng các số $x_k$ là bội của $ơ$. Câu trả\r\nlờ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ố\r\ntrong đoạn $[l_i,r_i]$\r\n\r\nBạn hãy giúp chú gấu Tommy giải bài toán này nhé!\r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên chứa số nguyên $n (1\\le n \\le 10^5)$\r\n\r\n- Dòng thứ 2 chứa n số nguyên dương $x_1, x_2, ..., x_n (2 \\le x_i \\le 10^7)$\r\n\r\n- Dòng thứ 3 chứa số nguyên $m (1 \\le m \\le 50000)$. Mỗi dòng $i$ trong $m$ dòng sau\r\nchứa 2 số nguyên ngăn cách bởi 1 dấu cách $l_i, r_i$ $(2 \\le l_i\r\n\\le r_i\r\n\\le 2\\times 10^9\r\n)$\r\n\r\n

Output

\r\n\r\n- 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.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 6\r\n 5 5 7 10 14 15\r\n 3\r\n 2 10\r\n 3 12\r\n 4 4\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 9\r\n 7\r\n 0\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n 3 truy vấn\r\n 1. Truy vấn 1: l = 2, r = 11.\r\n Ta cần tính: f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9.\r\n 2. Truy vấn 2: l = 3, r = 12.\r\n Ta cần tính: f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7.\r\n 3. Truy vấn 3: l = 4, r = 4 → không có số nguyên tố.","points":300.0,"partial":false,"time_limit":1.0,"memory_limit":512000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}