Một số nguyên dương ~n~ được phân tích thành thừa số nguyên tố như sau:

~n=p_1^{k_1}×p_2^{k_2}×…×p_m^{k_m}~

Yêu cầu: Cho hai số nguyên không âm ~a≤b~, dếm số lượng ước số của ~n~ thuộc ~[a,b]~.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương ~ m ~
• 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;
• 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 ứng một câu hỏi.

Kết quả

• Ghi trên ba dòng, mỗi dòng ghi ước số tìm được trả lời cho câu hỏi tương ứng ở dữ liệu vào.

Ràng buộc

• Có 40% số test ứng với ~ m ≤ 5; 0 ≤ a ≤ b ≤ 10^6 ~
• Có 40% số test ứng với ~ m ≤ 10; 0 ≤ a ≤ b ≤ 10^9 ~
• Có 20% số test ứng với ~ m ≤ 25; 0 ≤ a ≤ b ≤ 10^9 ~

Ví dụ:

Input 1

3
2 4
3 4
5 4
1 5
1 10
1 5 

Output 1

5
9
5