Để 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\) và \(r_i\). Gọi tập 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}\). \(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\) và \(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

2
1 5
3 7

23
34