Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Với mỗi số nguyên dương ~x~ có ít nhất hai chữ số, gọi ~f(x)~ là chữ số lớn thứ nhì của ~x~: xếp tất cả các chữ số của ~x~ theo thứ tự giảm dần (các chữ số giống nhau vẫn được tính riêng), ~f(x)~ là chữ số đứng ở vị trí thứ hai. Ví dụ: ~f(12) = 1~, ~f(20) = 0~, ~f(22) = 2~, ~f(1030) = 1~.

Cho hai số nguyên dương ~l, r~. Hãy tính ~f(l) + f(l + 1) + \cdots + f(r)~. Vì kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho ~7 \times 10^9 + 1~.

Input

• Dòng đầu tiên gồm một số nguyên dương ~t~ là số trường hợp thử nghiệm ~(1 \le t \le 15 \times 10^4)~.
• ~t~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~l, r~ ~(10 \le l \le r < 10^{18})~.

Output

Gồm ~t~ dòng, dòng thứ ~i~ là kết quả của trường hợp thử nghiệm thứ ~i~ sau khi chia lấy dư cho ~7 \times 10^9 + 1~.

Subtask

• Subtask 1 (~30\%~ số điểm): ~10 \le l \le r \le 10^6~.
• Subtask 2 (~40\%~ số điểm): ~t \le 69~ và ~r - l \le 10^6~.
• Subtask 3 (~30\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

2
12 24
1023 1030

Sample Output 1

15
15

Giải thích

Với trường hợp thử nghiệm thứ nhất: các số từ ~12~ đến ~19~ có chữ số lớn thứ nhì là ~1~; số ~20~ có chữ số lớn thứ nhì là ~0~; số ~21~ có chữ số lớn thứ nhì là ~1~; các số từ ~22~ đến ~24~ có chữ số lớn thứ nhì là ~2~. Vậy đáp án là ~1 \times 8 + 0 + 1 + 2 \times 3 = 15~.