Nezuko là \(1\) cô bé xinh đẹp, dễ thương, là em gái quốc dân, crush trong mơ của bao thằng wibu. Hôm nay Nezuko đã khám phá ra số “Wibu”. Số “Wibu” là \(1\) số tự nhiên mà tổng các chữ số nguyên tố cùng nhau với tổng \(wibu\) của các chữ số với \(wibu(i)=\)\(1^2+2^2+…+i^2\) \((0 \leq i \leq 9)\).

Ví dụ số \(20\), có tổng các chữ số là \(2+0=2\) và tổng \(wibu=wibu(2)\)\(+wibu(0)=5\) nguyên tố cùng nhau nên là số “Wibu”. Còn số \(33\) có tổng các chữ số là \(3+3=6\) và tổng \(wibu=wibu(3)\)\(+wibu(3)=28\) không nguyên tố cùng nhau nên không phải.

bin9638 cũng là \(1\) người crush Nezuko lâu năm. Bây giờ bin9638 đang muốn tính tổng các số “Wibu” trong đoạn từ \(l\) đến \(r\) \((l,r \leq 10^{18})\) để lấy le với Nezuko, nhưng khổ nỗi bây giờ bin9638 đang mãi hóng movie mới của Kimetsu No Yaiba nên không có thời gian tính toán. Các bạn hãy giúp bin9638 nhé.

Vì kết quả có thể rất lớn nên các bạn hãy in kết quả chia lấy dư cho \(10^9+7\).

Yêu cầu:

• Tính tổng các số “Wibu” trong đoạn \([l,r]\)

Input

• Dòng đầu tiên là số truy vấn \(q\) \((q ≤ 10^5)\).
• \(q\) dòng tiếp theo mỗi dòng là \(2\) số \(l,r\).

Output

• Gồm \(q\) dòng, mỗi dòng là kết quả cho truy vấn tương ứng.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(l,r \leq 10^6\), \(q ≤ 10\).

• Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.

Example

2
19 20
1 100

20
3268