24840번 - Challenge Nine 서브태스크다국어

문제

Ada gives John a positive integer $N$. She challenges him to construct a new number (without leading zeros), that is a multiple of 9ドル,ドル by inserting exactly one digit (0 …… 9) anywhere in the given number $N$. It is guaranteed that $N$ does not have any leading zeros.

As John prefers smaller numbers, he wants to construct the smallest such number possible. Can you help John?

입력

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

Each test case has a single line containing a positive integer $N$: the number Ada gives John.

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the new number constructed by John. As mentioned earlier, $y$ cannot have leading zeros.

제한

• 1ドル≤T≤100$.

Test Set 1 (8점)

시간 제한: 20 초

• 1ドル≤N≤10^5$.

Test Set 2 (12점)

시간 제한: 40 초

For at most 10 cases:

• 1ドル≤N≤10^{123456}$.

For the remaining cases:

• 1ドル≤N≤10^5$.

힌트

In Sample Case #1, there are only two numbers that can be constructed satisfying the divisibility constraint: 45ドル$ and 54ドル$. John chooses the smaller number.

In Sample Case #2, 333ドル$ is the only number possible.

In Sample Case #3, there are four possible options - 212121ドル,ドル 122121ドル,ドル 121221ドル$ and 121212ドル$ - out of which the smallest number is 121212ドル$.