Bạn có bao giờ cảm thấy thất vọng với truyền hình vì cứ phải xem đi xem lại những thứ giống nhau, được "tái chế" (recycled) liên tục không? Cá nhân tôi thì không quan tâm đến truyền hình lắm, nhưng đôi khi tôi lại cảm thấy như vậy về các con số.

Giả sử một cặp số nguyên dương phân biệt \((n, m)\) được gọi là tái chế nếu bạn có thể nhận được \(m\) bằng cách chuyển một số chữ số từ cuối của \(n\) lên đầu mà không làm thay đổi thứ tự của chúng. Ví dụ, \((12345, 34512)\) là một cặp tái chế vì bạn có thể nhận được \(34512\) bằng cách chuyển \(345\) từ cuối của \(12345\) lên đầu. Lưu ý rằng \(n\) và \(m\) phải có cùng số lượng chữ số để trở thành một cặp tái chế. Cả \(n\) và \(m\) đều không được có chữ số \(0\) ở đầu.

Cho các số nguyên \(A\) và \(B\) có cùng số lượng chữ số và không có chữ số \(0\) ở đầu, có bao nhiêu cặp tái chế phân biệt \((n, m)\) thỏa mãn \(A \le n < m \le B\)?

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 gồm một dòng duy nhất chứa các số nguyên \(A\) và \(B\).

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1), và y là số lượng cặp tái chế \((n, m)\) với \(A \le n < m \le B\).

Ràng buộc

• \(1 \le T \le 50\).
• \(A\) và \(B\) có cùng số lượng chữ số.

Phân nhóm

• Tập kiểm tra 1 (Visible Verdict): \(1 \le A \le B \le 1000\).
• Tập kiểm tra 2 (Hidden Verdict): \(1 \le A \le B \le 2000000\).

Đ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ụ

4
1 9
10 40
100 500
1111 2222

Case #1: 0
Case #2: 3
Case #3: 156
Case #4: 287

Nguồn

Google Code Jam 2012, Vòng loại, bài Recycled Numbers.

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