Ngày xửa ngày xưa trong một tình huống kỳ lạ, người ta gọi một số là xấu xí (ugly) nếu nó chia hết cho bất kỳ số nguyên tố có một chữ số nào (\(2, 3, 5\) hoặc \(7\)). Vì vậy, \(14\) là số xấu xí, nhưng \(13\) thì không. \(39\) là số xấu xí, nhưng \(121\) thì không. Lưu ý rằng \(0\) là số xấu xí. Ngoài ra, các số âm cũng có thể là số xấu xí; \(-14\) và \(-39\) là những ví dụ về các số như vậy.

Vào một ngày rảnh rỗi, bạn đang ngắm nhìn một chuỗi các chữ số, chẳng hạn như:

123456

Bạn cảm thấy thú vị bởi có bao nhiêu khả năng xảy ra nếu bạn được phép chèn các dấu cộng (\(+\)) hoặc trừ (\(-\)) vào giữa các chữ số. Ví dụ, bạn có thể tạo ra:

1 + 234 - 5 + 6 = 236

là một số xấu xí. Hoặc:

123 + 4 - 56 = 71

không phải là một số xấu xí.

Rất dễ để đếm số cách khác nhau mà bạn có thể chơi với các chữ số: Giữa mỗi hai chữ số liền kề, bạn có thể chọn đặt một dấu cộng, một dấu trừ hoặc không đặt gì cả. Do đó, nếu bạn bắt đầu với \(D\) chữ số, có \(3^{D-1}\) biểu thức bạn có thể tạo ra.

Lưu ý rằng việc có các số không ở đầu là hoàn toàn hợp lệ. Nếu chuỗi là "01023", thì "01023", "0+1-02+3" và "01-023" đều là các biểu thức hợp lệ.

Nhiệm vụ của bạn rất đơn giản: Trong số \(3^{D-1}\) biểu thức đó, hãy đếm xem có bao nhiêu biểu thức có giá trị là một số xấu xí.

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số lượng bộ dữ liệu, \(N\). Mỗi bộ dữ liệu sẽ là một dòng duy nhất chứa một chuỗi các chữ số thập phân không rỗng.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, bạn nên xuất ra một dòng:

Case #X: Y

trong đó \(X\) là số thứ tự bộ dữ liệu, bắt đầu từ 1, và \(Y\) là số lượng biểu thức có giá trị là một số xấu xí.

Ràng buộc

• \(0 \le N \le 100\).
• Chuỗi trong mỗi bộ dữ liệu sẽ không rỗng và chỉ chứa các ký tự từ '0' đến '9'.

Phân nhóm

• Small dataset (Test set 1 - Visible): Mỗi chuỗi dài không quá 13 ký tự.
• Large dataset (Test set 2 - Hidden): Mỗi chuỗi dài không quá 40 ký tự.

Đ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
011
12345

Case #1: 0
Case #2: 1
Case #3: 6
Case #4: 64

Nguồn

Google Code Jam 2008, Vòng 1C, bài Ugly 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.