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 đoạn \([A, B]\).

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• 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.

Output

• 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
  ứng ở dữ liệu vào.

Scoring

• 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\)

Example

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

5
9
5