LIS nhưng là một version khác

Mọi người đều đã quen thuộc với bài toán tìm LIS (Longest Increasing Subsequence) của một dãy số. Tuy nhiên, Ami lại có một sở thích hơi khác. Thay vì nghiên cứu một dãy số, cậu chỉ nhìn vào các chữ số của một số nguyên.

Ami định nghĩa LIDS (Longest Increasing Digit Subsequence) của một số nguyên là độ dài của dãy con tăng dài nhất được tạo bởi các chữ số của số đó.

Ví dụ:

• LIDS của \(1234\) có độ dài \(4\).
• LIDS của \(12234\) có độ dài \(4\).
• LIDS của \(456123\) có độ dài \(3\).

Một số ví dụ về dãy chữ số tăng hợp lệ là:

Trong khi đó,

không phải là dãy tăng.

Cho hai số nguyên \(L\) và \(R\).

Yêu cầu. Trong tất cả các số nguyên thuộc đoạn \([L,R]\):

• Tìm giá trị lớn nhất của LIDS.
• Đếm số cách tạo ra LIDS lớn nhất đó.

Hai cách được coi là khác nhau nếu:

• Hai dãy chữ số thu được khác nhau; hoặc
• Chúng được lấy từ các vị trí khác nhau trong cùng một số.

\InputFile

Dòng đầu chứa số nguyên \(T\) \((1 \le T \le 10^4)\) là số lượng bộ dữ liệu.

Mỗi bộ dữ liệu gồm một dòng chứa hai số nguyên

thỏa mãn

\OutputFile

Với mỗi bộ dữ liệu, in ra một dòng theo định dạng

\begincenter
Case x: a b
\endcenter

trong đó:

• \(x\) là số thứ tự bộ dữ liệu (bắt đầu từ \(1\));
• \(a\) là độ dài lớn nhất của LIDS trong đoạn;
• \(b\) là số cách tạo ra LIDS có độ dài lớn nhất.

\Examples

\beginexample
\exmp
2
111 114
15432 15432

Case 1: 2 6
Case 2: 2 4

\endexample

\Note

Ở bộ dữ liệu thứ nhất:

• LIDS của \(111\) có độ dài \(1\).
• LIDS của \(112\), \(113\) và \(114\) đều có độ dài \(2\).

Do đó, độ dài LIDS lớn nhất là \(2\) và có tổng cộng \(6\) cách tạo ra các dãy con tăng có độ dài này.

Ở bộ dữ liệu thứ hai, số \(15432\) có LIDS bằng \(2\). Có bốn cách đạt được giá trị này:

\endproblem