Cho một số nguyên \(N\), thay thế nó bằng tổng bình phương các chữ số của nó. Một số hạnh phúc (happy number) là một số mà nếu bạn áp dụng quy trình này lặp đi lặp lại, cuối cùng nó sẽ dẫn đến kết quả là 1. Ví dụ, nếu bạn bắt đầu với 82:

8*8 + 2*2       = 64 + 4    = 68,  repeat:
6*6 + 8*8       = 36 + 64   = 100, repeat:
1*1 + 0*0 + 0*0 = 1 + 0 + 0 = 1 (happy! :)

Vì quy trình này dẫn đến 1, nên 82 là một số hạnh phúc.

Lưu ý rằng một số có thể là số hạnh phúc trong một số hệ cơ số này, nhưng không hạnh phúc trong các hệ cơ số khác. Ví dụ, số 82 ở hệ cơ số 10 không phải là số hạnh phúc khi viết ở hệ cơ số 3 (dưới dạng 10001).

Bạn là một trong những thám tử số học hàng đầu thế giới. Một số hệ cơ số đã tập hợp lại và thuê bạn cho một nhiệm vụ quan trọng: tìm số nguyên nhỏ nhất lớn hơn 1 mà là số hạnh phúc trong tất cả các hệ cơ số đã cho.

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 tiếp theo. Mỗi bộ test bao gồm một dòng duy nhất. Mỗi dòng chứa một danh sách các số nguyên phân biệt cách nhau bởi dấu cách, đại diện cho các hệ cơ số. Danh sách các hệ cơ số luôn được sắp xếp theo thứ tự tăng dần.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất:

Case #X: K

trong đó X là số thứ tự bộ test, bắt đầu từ 1, và K là biểu diễn thập phân của số nguyên nhỏ nhất (lớn hơn 1) là số hạnh phúc trong tất cả các hệ cơ số đã cho.

Ràng buộc

• \(2 \le\) tất cả các hệ cơ số đầu vào có thể có \(\le 10\).

Phân nhóm

• Small dataset: \(1 \le \mathbf{T} \le 42\); \(2 \le\) số lượng hệ cơ số trong mỗi bộ test \(\le 3\).
• Large dataset: \(1 \le \mathbf{T} \le 500\); \(2 \le\) số lượng hệ cơ số trong mỗi bộ test \(\le 9\).

Đ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
2 3
2 3 7
9 10

Case #1: 3
Case #2: 143
Case #3: 91

Ghi chú quan trọng

Vui lòng nhớ rằng bạn phải nộp tất cả mã nguồn được sử dụng để giải bài toán này.

Nguồn

Google Code Jam 2009, Vòng 1A, bài Multi-base happiness.

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