Để chào đón sự trở về của các anh hùng Đội tuyển quốc gia Việt Nam, thtb8 muốn phamgiaminh trả lời ~T~ bài toán, bài toán thứ ~i~ gồm hai số nguyên dương ~l_i~ và ~r_i~. Gọi tập các số nguyên tố nằm trong khoảng giữa ~l_i~ và ~r_i~ được sắp xếp theo thứ tự tăng dần là

~S =~ {~p_1,p_2,...,p_k~}. thtb8 cần phamgiaminh tính công thức sau:

Vì kết quả có thể rất lớn nên thtb8 muốn phamgiaminh trả lời các kết quả là phần dư khi chia cho ~10^9+7~. phamgiaminh khá buồn vì Park Hang Seo chia tay VN nên muốn nhờ các bạn giúp phamgiaminh trả lời các bài toán đó.

Dữ liệu

• Dòng đầu tiên ghi một số nguyên dương ~T~ là số lượng bài toán.

• Dòng thứ ~i~ trong ~T~ dòng tiếp theo gồm ~2~ số nguyên dương ~l_i~ và ~r_i~.

• ~l_i,r_i, T ≤ 10^6~

Kết quả

• In ra ~T~ dòng, dòng thứ ~i~ là kết quả của bài toán thứ ~i~.

Sample

Input

2
1 5
3 7

Output

23
34