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} \times p_2^{k_2} \times ... \times p_m^{k_m}~

Cho ~A < B~, đếm số lượng ước của ~n~ thuộc đoạn ~[A, B]~?

Dữ liệu:

• Dòng đầu chứa số ~m~ ~(m < 100)~;
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~p_i~ và ~k_i~ ~(p_i, k_i < 10^9)~;
• ~3~ dòng cuối tương ứng với ~3~ truy vấn, mỗi dòng chứa hai số nguyên ~A, B~ tương ứng với một truy vấn ~(0 < A < B < 10^9)~.

Kết quả:

• Ghi ra ~3~ dòng, mỗi dòng ghi số ước số tìm được trả lời cho truy vấn tương ứng ở dữ liệu vào.

Ví dụ:

Input

4
2  3
3  4
5  7
7  2
1  6
2  11
1  1000 

**Output

6
9
101

Ràng buộc:

• Có ~50\%~ số tests ứng với ~50\%~ số điểm của bài có ~m < 5; 0 < A < B < 10^6~