Won't sum? Must now 20s 1024MB

Problems

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 S, find K palindromic terms that sum to S, such that K is minimized.

Input

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

Output

For each test case, output one line of the form Case #x: A₁ (if only one term is needed), Case #x: A₁ A₂ (if only two terms are needed), or Case #x: A₁ A₂ A₃ (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_is equals S.

Example

3keyboard_return
1keyboard_return
198keyboard_return
1234567890

Casespace_bar #1:space_bar 1keyboard_return
Casespace_bar #2:space_bar 191space_bar 7keyboard_return
Casespace_bar #3:space_bar 672787276space_bar 94449space_bar 561686165

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.

Source

GCJ 2019wf C

You must sign in to write code.

#10351 upload 1 done - how_to_reg -

Won&#039;t sum? Must now timer 20s memory 1024MB

Problems translate English text_fields