Một số nguyên dương được gọi là số đối xứng (palindrome) nếu biểu diễn thập phân của nó (không có các chữ số 0 ở đầu) là một chuỗi đối xứng (đọc từ trái sang phải hay từ phải sang trái đều giống nhau). Ví dụ: các số 5, 77, 363, 4884, 11111, 12121 và 349943 là các số đối xứng.

Một đoạn các số nguyên được gọi là thú vị nếu nó chứa một số lượng chẵn các số đối xứng. Đoạn \([L, R]\) với \(L \le R\) được định nghĩa là dãy các số nguyên từ \(L\) đến \(R\) (bao gồm cả hai đầu): \((L, L+1, L+2, \dots, R-1, R)\). \(L\) và \(R\) lần lượt là số đầu tiên và số cuối cùng của đoạn.

Đoạn \([L_1, R_1]\) được gọi là đoạn con của \([L, R]\) nếu \(L \le L_1 \le R_1 \le R\). Nhiệm vụ của bạn là xác định xem có bao nhiêu đoạn con thú vị của \([L, R]\).

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, T. T bộ test theo sau. Mỗi bộ test nằm trên một dòng chứa hai số nguyên dương L và R (theo thứ tự đó), cách nhau bởi một khoảng trắng.

Dữ liệu ra

Với mỗi bộ test, xuất ra một dòng. Dòng đó phải chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng đoạn con thú vị của \([L, R]\), lấy modulo \(1000000007\).

Ràng buộc

• \(1 \le \mathbf{T} \le 120\)

Phân nhóm

• Small dataset: \(1 \le \mathbf{L} \le \mathbf{R} \le 10^{13}\)
• Large dataset: \(1 \le \mathbf{L} \le \mathbf{R} \le 10^{100}\)

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
1 2
1 7
12 110

Case #1: 1
Case #2: 12
Case #3: 2466

Nguồn

Google Code Jam 2009, Vòng 3, bài Interesting Ranges.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.