题目描述

In 2016, it was shown that every positive integer can be written as the sum of three or fewer palindromic terms. For the purposes of this problem, a palindromic term is a string of digits (with no leading zeroes) that represents a positive integer and reads the same forward and backward.

Given a positive integer $\mathbf{S}$, find $\mathbf{K}$ palindromic terms that sum to $\mathbf{S}$, such that $\mathbf{K}$ is minimized.

输入格式

The first line of input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ lines follow, each containing a positive integer $\mathbf{S}$.

输出格式

For each test case, output one line of the form Case #x: $A_1$ (if only one term is needed), Case #x: $A_1$ $A_2$ (if only two terms are needed), or Case #x: $A_1$ $A_2$ $A_3$ (if three terms are needed), where $x$ is the case number (counting starting from 1), each $A_i$ is a palindromic term (as described above), and the sum of the $A_i$s equals $\mathbf{S}$.

3
1
198
1234567890

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

提示

Sample Explanation

In Sample Case #1, the input is already a palindrome.

In Sample Case #2, note that 99 99, for example, would also be an acceptable answer. Even though there are multiple instances of 99, they count as separate terms, so this solution uses the same number of terms as 191 7.

Also note that 191 07, 181 8 9, 0110 88, 101 97, 7.0 191.0, and -202 4, for example, would not be acceptable answers.

Limits

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

Test set 1 (5 Pts, Visible)

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

Test set 2 (22 Pts, Hidden)

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