Cho \(T\) truy vấn, truy vấn thứ \(i\) gồm \(2\) số nguyên dương \(a_i, b_i\).

Yêu cầu

• Trả lời \(T\) truy vấn, ứng với truy vấn thứ \(i\), tính tổng các số nguyên tố nằm trong đoạn \([a_i; b_i]\).

Dữ liệu vào

• Dòng thứ nhất chứa số duy nhất số nguyên dương \(T\).
• Dòng thứ \(i\) trong \(T\) dòng tiếp theo chứa \(2\) số nguyên dương \(a_i, b_i\).
• Các số trên cùng một dòng cách nhau bởi một kí tự trắng.

Dữ liệu đảm bảo:

• \(1 \le a_i \le b_i \le 10^5\).
• \(1 \le T \le 10^5\).

Dữ liệu ra

• Gồm \(T\) dòng, dòng thứ \(i\) chứa một số nguyên dương duy nhất là đáp án của truy vấn thứ \(i\).

Ràng buộc

• Có \(20\%\) số test có \(T =\) \(1,\) \(1 \le a_i, b_i \le 10^3\).
• Có \(40\%\) số test có \(T \le 10^3\); \(1 \le a_i, b_i \le 10^4\).
• Có \(40\%\) số test còn lại không có ràng buộc gì thêm.

Input 1

2
1 20
10 19

Output 1

77
60