Description

2016 年，有研究表明每个正整数都可以表示为不超过三个回文数之和。在本题中，回文数指的是没有前导零、正读和反读都相同的正整数。

给定一个正整数 $\mathbf{S}$，请找出 $\mathbf{K}$ 个回文数，使它们的和等于 $\mathbf{S}$，并且 $\mathbf{K}$ 最小。

Input Format

输入的第一行为测试用例数 $\mathbf{T}$。接下来的 $\mathbf{T}$ 行，每行包含一个正整数 $\mathbf{S}$。

Output Format

对于每个测试用例，输出一行，格式为 Case #x: $A_1$（如果只需要一个回文数）、Case #x: $A_1$ $A_2$（如果需要两个回文数），或 Case #x: $A_1$ $A_2$ $A_3$（如果需要三个回文数），其中 $x$ 为测试用例编号（从 1 开始），每个 $A_i$ 为一个回文数，且 $A_1 + A_2 + \cdots + A_K = \mathbf{S}$。

3
1
198
1234567890

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

Hint

样例解释

在样例第 1 个用例中，输入本身就是回文数。

在样例第 2 个用例中，99 99 也是一个可行答案。即使有多个 99，它们也算作不同的项，因此这个解法和 191 7 使用的项数相同。

注意，191 07、181 8 9、0110 88、101 97、7.0 191.0、-202 4 等都不是可接受的答案。

数据范围

• $1 \leq \mathbf{T} \leq 100$。

测试点 1（5 分，可见）

• $1 \leq \mathbf{S} \leq 10^{10}$。

测试点 2（22 分，隐藏）

• $1 \leq \mathbf{S} \leq 10^{40}$。

由 ChatGPT 4.1 翻译