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

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]\).

Input

• Dòng thứ nhất chứa số duy nhất số nguyên dương \(T\) (\(1 \leq T \leq 10^5\));
• 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.

Output

• Ghi ra \(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\).

Example

2
1 20
10 19

77
60

Scoring

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