Đề bài

Viết chương trình tính tổng của các số nguyên tố nằm trong đoạn [L, R] cho trước.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên dương T, là số bộ dữ liệu thử nghiệm. (1 ≤ T ≤ 106)
• T dòng tiếp theo, mỗi dòng gồm hai số nguyên dương L và R, giới hạn của đoạn. (1 ≤ L ≤ R ≤ 106)

Kết quả

Ghi kết quả ra gồm T dòng, mỗi dòng ghi kết quả tổng của các số nguyên tố nằm trong đoạn [L, R] tương ứng.

Ví dụ

Input

2
1 10
10 20

Output

17
60

Ràng buộc

• Subtask 1: 60% số bộ test có 1 ≤ T ≤ 100 và 1 ≤ L, R ≤ 106.
• Subtask 2: 40% số bộ test có 1 ≤ T ≤ 106 và 1 ≤ L, R ≤ 106.