Năm 2016, người ta đã chứng minh rằng mọi số nguyên dương đều có thể viết thành tổng của không quá ba số hạng palindrome. Trong bài này, một số hạng palindrome là chuỗi chữ số không có số 0 ở đầu, biểu diễn một số nguyên dương và đọc xuôi hay ngược đều giống nhau.

Cho số nguyên dương \(S\), hãy tìm \(K\) số hạng palindrome có tổng bằng \(S\), sao cho \(K\) nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi dòng trong \(T\) dòng tiếp theo chứa một số nguyên dương \(S\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo một trong các dạng Case #x: A1 nếu chỉ cần một số hạng, Case #x: A1 A2 nếu cần hai số hạng, hoặc Case #x: A1 A2 A3 nếu cần ba số hạng. x là số thứ tự bộ test (bắt đầu từ 1), mỗi \(A_i\) là một số hạng palindrome như định nghĩa trên, và tổng các \(A_i\) bằng \(S\).

Ràng buộc

• \(1\le T\le100\).

Phân nhóm

Test Set 1 (Visible): \(1\le S\le10^{10}\).

Test Set 2 (Hidden): \(1\le S\le10^{40}\).

Đ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
1
198
1234567890

Case #1: 1
Case #2: 191 7
Case #3: 672787276 94449 561686165

Nguồn

Google Code Jam 2019, Chung kết thế giới, bài Won't sum? Must now.

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