PRIME

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Để chào đón sự trở về của các chàng trai đá VOI trở về, \(camuc\) muốn \(bedihoc\) trả lời \(T\) bài toán, bài toán thứ \(i\) gồm hai số nguyên dương \(l_i\)\(r_i\). Gọi tập tập các số nguyên tố nằm trong khoảng giữa \(l_i\)\(r_i\) được sắp xếp theo thứ tự tăng dần là \(S = {p_1,p_2, ...,p_k}\). \(canuc\) cần \(bedihoc\) tính công thức sau:

\(\(f_i=\sum_{j=1}^{k}j * p_j\)\)

Vì kết quả có thể rất lớn nên \(canuc\) muốn \(bedihoc\) trả lời các kết quả là phần dư khi chia cho \(10^9 + 7\).

\(bedihoc\) khá buồn vì đá VOI toàn khù khờ nên muốn nhờ các bạn giúp \(bedihoc\) trả lời các bài toán đó.

Input

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

Output

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

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(\sum_{i=1}^{T} |r_i — l_i| \lt 10^3, l_i,r_i,T \lt 10^3\)
  • Subtask \(2\) (\(20\%\) số điểm): \(\sum_{i=1}^{T} |r_i — l_i| \lt 10^6, l_i,r_i,T \lt 10^6\)
  • Subtask \(3\) (\(60\%\) số điểm): \(l_i,r_i,T \lt 10^6\)

Example

Test 1

Input
2
1 5
3 7
Output
23
34

Bình luận


  • -8
    algorit    12:53 p.m. 22 Tháng 1, 2021

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.