Mô tả

Cho ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~L~ và ~R~ ~(1 \leq L \leq R \leq 10^6)~. Với mỗi truy vấn, bạn cần tính tổng các số nguyên tố trong đoạn ~[L,R]~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~Q~ ~(1 \leq Q \leq 10^5)~ ~-~ số lượng truy vấn.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~ ~(1 \leq L \leq R \leq 10^6)~.

Output

Gồm ~Q~ dòng, mỗi dòng ứng với mỗi truy vấn, in ra một số duy nhất là tổng các số nguyên tố trong đoạn ~[L,R]~.

Ví dụ

Input

3
1 10
5 15
1 5

Output

17
36
10

Giải thích

• Truy vấn 1: Các số nguyên tố trong đoạn ~[1,10]~ là ~2, 3, 5, 7~. Tổng ~= 17~.
• Truy vấn 2: Các số nguyên tố trong đoạn ~[5,15]~ là ~5, 7, 11, 13~. Tổng ~= 36~.
• Truy vấn 3: Các số nguyên tố trong đoạn ~[1,5]~ là ~2, 3, 5~. Tổng ~= 10~.