Mỗi bài tập chỉ được phép nộp ~2~ lần trong suốt contest.

Với mỗi số nguyên ~n~, ta gọi ~G_n~ là tổng tất cả các ước nguyên tố của ~n~. Bạn được cho ~T~ cặp số ~l~ và ~r~, nhiệm vụ của bạn là hãy tính tổng ~G_i~ với ~l \le i \le r~.

Dữ liệu

Nhập từ file sumdiv.inp:

• Dòng đầu tiên là số nguyên ~T~ ~(1 \le T \le 10^6)~.
• ~T~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~l~ và ~r~ ~(1 \le l \le r \le 10^6)~, cách nhau bởi dấu cách.

Kết quả

• Xuất ra file sum.out ~T~ số nguyên là kết quả cần tìm sau khi chia lấy phần dư cho ~1000000007~, mỗi số nằm trên một dòng.

Giới hạn

• Subtask ~1~ ~(20\%)~: ~T \le 10~ và ~r \le 1000~.
• Subtask ~2~ ~(50\%)~: ~T \le 100~ và ~r \le 10^4~.
• Subtask ~3~ ~(30\%)~: không có giới hạn nào thêm.

Ví dụ

Dữ liệu

2
1 2
1 3

Kết quả

2
5

Giải thích

• Ở testcase đầu tiên, ~G_1 = 0, G_2 = 2, G_1 + G_2 = 0 + 2 = 2~