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 \le B~, đếm số lượng ước của ~n~ trong thuộc ~[A, B]~.

Dữ liệu

• 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 với một câu hỏi.

Kết quả

• Ghi ra 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:

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

Sample Input

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

Sample Output

5
9
5