시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 (추가 시간 없음) 1024 MB0000.000%

문제

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.

입력

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

출력

For each test case, output one line of the form Case #x: A1 (if only one term is needed), Case #x: A1 A2 (if only two terms are needed), or Case #x: A1 A2 A3 (if three terms are needed), where x is the case number (counting starting from 1), each Ai is a palindromic term (as described above), and the sum of the Ais equals S.

제한

  • 1 ≤ T ≤ 100.

Test Set 1 (5점)

  • 1 ≤ S ≤ 1010.

Test Set 2 (22점)

  • 1 ≤ S ≤ 1040.

예제 입력 1

3
1
198
1234567890

예제 출력 1

Case #1: 1
Case #2: 191 7
Case #3: 672787276 94449 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.

채점 및 기타 정보

  • 예제는 채점하지 않는다.