Monkey D. Luffy và băng hải tặc Mũ Rơm đang dong buồm vượt qua những vùng biển khắc nghiệt của Tân Thế Giới để tiến gần hơn đến hòn đảo cuối cùng Laugh Tale. Một ngày nọ, khi đang quan sát chiếc kim chỉ nam vĩnh cửu (Log Pose) đặc biệt dùng để dẫn đường qua một vùng biển đầy sương mù, hoa tiêu Nami phát hiện ra rằng từ trường của các hòn đảo nơi đây biến đổi theo những dãy số tọa độ khổng lồ. Nếu đi chệch khỏi luồng từ trường ổn định, con tàu Thousand Sunny sẽ lập tức bị cuốn vào những cơn bão xoáy nguy hiểm. Bị cuốn hút bởi hiện tượng kỳ lạ này, nhà khảo cổ học Nico Robin đã đối chiếu với một văn bản cổ và biết được rằng đây là "Vùng Biển Cân Bằng" – nơi chỉ những tọa độ đạt trạng thái hài hòa tuyệt đối mới dẫn lối đến các hòn đảo an toàn.

Để giúp tàu Thousand Sunny vượt qua vùng biển này, Nami quyết định lập bản đồ hàng hải dựa trên cấu trúc toán học của từ trường:

• Cấu trúc tọa độ cân bằng:
  • Mỗi tọa độ trên biển được biểu diễn bằng một số nguyên dương trong hệ thập phân (không tính các chữ số ~0~ vô nghĩa ở đầu). Một số nguyên dương được gọi là số cân bằng nếu trong biểu diễn thập phân của nó, số lượng chữ số chẵn bằng số lượng chữ số lẻ (các chữ số chẵn gồm ~0, 2, 4, 6, 8~; các chữ số lẻ gồm ~1, 3, 5, 7, 9~).

• Quy tắc định vị hải trình: Trước mắt băng Mũ Rơm là ~Q~ vùng biển liên tiếp cần phải khảo sát:
  • Với mỗi vùng biển thứ ~i~, Nami xác định được phạm vi tọa độ trải dài từ ~L~ đến ~R~.
  • Nhiệm vụ của cô là phải đếm số lượng số cân bằng thuộc đoạn ~[L, R]~ để ước tính số lượng hải đảo an toàn có thể neo đậu.

Vì tọa độ ở Tân Thế Giới là những con số cực kỳ khổng lồ (có thể lên tới hàng trăm nghìn chữ số), kết quả đếm được cũng sẽ rất lớn. Do đó, Nami chỉ cần biết phần dư của số lượng tìm được khi chia cho ~10^9 + 7~. Bạn hãy lập trình giúp hoa tiêu Nami tính toán thật nhanh các thông số này để băng Mũ Rơm tiếp tục cuộc phiêu lưu nhé!

Input

• Dòng đầu tiên chứa một số nguyên dương ~Q~ là số lượng vùng biển cần khảo sát ~(Q \leq 1000)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~L~ và ~R~ cách nhau bởi một khoảng trắng thể hiện phạm vi tọa độ của vùng biển ~(1 \leq L \leq R \leq 10^{100000})~.

Output

• Gồm ~Q~ dòng, mỗi dòng in ra một số nguyên duy nhất là số lượng số cân bằng trong đoạn ~[L, R]~ tương ứng sau khi chia lấy dư cho ~10^9 + 7~.

Example Input

1
1 20

Example Output

5

Giải thích

• Trong đoạn từ ~1~ đến ~20~, các số có ~1~ chữ số (từ ~1~ đến ~9~) đều chỉ có ~1~ chữ số chẵn hoặc ~1~ chữ số lẻ nên không có số nào cân bằng.
• Xét các số có 2 chữ số từ ~10~ đến ~20~, các số có đúng ~1~ chữ số chẵn và ~1~ chữ số lẻ bao gồm: ~10, 12, 14, 16, 18~.
• Vậy có tất cả ~5~ số cân bằng trong đoạn ~[1, 20]~.

Ràng buộc

Gọi ~|S|~ là số lượng chữ số trong biểu diễn thập phân của ~S~.

• Subtask ~1~ (~15\%~ số điểm): ~Q \leq 100~ và ~R \leq 1000~.
• Subtask ~2~ (~15\%~ số điểm): ~R \leq 10^6~.
• Subtask ~3~ (~15\%~ số điểm): ~R \leq 10^9~.
• Subtask ~4~ (~15\%~ số điểm): ~L = 1, R = 10^k~ ~(k \leq 10)~.
• Subtask ~5~ (~15\%~ số điểm): ~R \leq 10^{18}~.
• Subtask ~6~ (~5\%~ số điểm): ~L = 1, R = 10^k~ ~(k \leq 10^4)~.
• Subtask ~7~ (~5\%~ số điểm): ~Q \leq 100~ và ~|L|, |R| \leq 100~.
• Subtask ~8~ (~5\%~ số điểm): ~Q \leq 100~ và ~|L|, |R| \leq 1000~.
• Subtask ~9~ (~5\%~ số điểm): ~Q \leq 100~ và ~|L|, |R| \leq 10^4~.
• Subtask ~10~ (~5\%~ số điểm): ~Q \leq 100~.