{"code":"21thtskb2","name":"Ước số (THTB Vòng Sơ loại)","description":"Một số nguyên dương $n$ được phân tích thành thừa số nguyên tố như sau:\r\n\r\n$n = p_1^{k_1} × p_2^{k_2} × ... × p_m^{k_m}$\r\n\r\nYêu cầu: Cho hai số nguyên không âm $A \\le B$, đếm số lượng ước của $n$ trong đoạn $[A, B]$.\r\n\r\n

Input

\r\n\r\nVào từ thiết bị vào chuẩn có khuôn dạng:\r\n- Dòng đầu chứa số nguyên dương $m$;\r\n- Tiếp theo là $m$ dòng, dòng thứ $i$ chứa hai số nguyên dương $p_i$ và $k_i$, trong đó $p_i$, $k_i$ không vượt quá $10^9$ và các số $p_i$ là số nguyên tố đôi một khác nhau;\r\n\r\n- Ba dòng cuối tương ứng với ba câu hỏi, mỗi dòng chứa hai số nguyên không âm $A, B$ tương\r\nứng với một câu hỏi.\r\n\r\n

Output

\r\n\r\n- Ghi ra thiết bị ra chuẩn ba dòng, mỗi dòng ghi ước số tìm được trả lời cho câu hỏi tương\r\nứng ở dữ liệu vào.\r\n\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ (%40\\%$ số điểm): $m \\le 5; 0 \\le A \\le B \\le 10^6$;\r\n- Subtask $2$ (%40\\%$ số điểm): $m \\le 10; 0 \\le A \\le B \\le 10^9$;\r\n- Subtask $3$ (%20\\%$ số điểm): $m \\le 25; 0 \\le A \\le B \\le 10^9$\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3\r\n 2 4\r\n 3 4\r\n 5 4\r\n 1 5\r\n 1 10\r\n 1 5\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 5\r\n 9\r\n 5\r\n ```","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"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}}