Các nhà hóa học nghiên cứu những nguyên tố trong bảng tuần hoàn, còn tại Code Jam, chúng tôi dùng máy nghiền số tiên tiến để nghiên cứu googlement. Một googlement là một chất có thể biểu diễn bằng chuỗi nhiều nhất chín chữ số. Googlement độ dài \(L\) chỉ được chứa các chữ số thập phân từ \(0\) đến \(L\), kể cả hai đầu, và phải có ít nhất một chữ số lớn hơn \(0\). Được phép có số \(0\) ở đầu. Chẳng hạn, 103 và 001 là googlement hợp lệ độ dài \(3\); 400 không hợp lệ vì chứa chữ số \(4\) lớn hơn độ dài \(3\), còn 000 không hợp lệ vì không có chữ số nào lớn hơn \(0\).

Mọi googlement hợp lệ có thể xuất hiện trên thế giới vào bất kỳ lúc nào, nhưng rồi sẽ phân rã tất định thành một googlement khác. Với googlement độ dài \(L\), hãy đếm số chữ số 1 trong nó (có thể bằng \(0\)) và ghi kết quả; tiếp tục đếm số chữ số 2 rồi ghi kết quả bên phải; cứ như vậy cho đến khi đếm và ghi số chữ số \(L\). Chuỗi mới tạo ra biểu diễn googlement mới và vẫn có độ dài \(L\). Thậm chí một googlement có thể phân rã thành chính nó.

Ví dụ, googlement 0414 vừa xuất hiện. Nó có một chữ số 1, không có 2, không có 3 và có hai chữ số 4, nên phân rã thành 1002. Chuỗi này có một 1, một 2, không có 3 và không có 4, nên phân rã thành 1100; sau đó lần lượt thành 2000, 0100, 1000, rồi 1000 tiếp tục phân rã thành chính nó mãi mãi.

Bạn vừa quan sát một googlement \(G\). Nó có thể vừa xuất hiện, hoặc có thể là kết quả của một hay nhiều bước phân rã. Hỏi tổng số googlement khác nhau có thể là trạng thái của nó khi mới xuất hiện trên thế giới.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa chuỗi \(G\), biểu diễn googlement quan sát được.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ \(1\), và y là số googlement khác nhau mà googlement quan sát được có thể từng là khi mới xuất hiện.

Ràng buộc

• \(1\le T\le100\).
• Mỗi chữ số trong \(G\) nằm từ \(0\) đến \(|G|\), kể cả hai đầu.
• \(G\) chứa ít nhất một chữ số khác \(0\).

Phân nhóm

Test Set 1 (Visible): \(1\le|G|\le5\).

Test Set 2 (Hidden): \(1\le|G|\le9\).

Đ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
20
1
123

Case #1: 4
Case #2: 1
Case #3: 1

Nguồn

Google Code Jam 2017, Vòng 3, bài Googlements.

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