Hide That Number

Time limit1sMemory limit128 MB

Summary
Given the disguised value (11 times the original, truncated to the original's digit count), recover the original number or report IMPOSSIBLE.
Level

Medium6 of 10

Topics
Math, Number theory, Implementation, String matching
Solved
No attempts yet

Problem

Alex is paranoid about anyone getting hold of his phone book, so he records every phone number in a disguised form that only he can decode. His method is the following.

Instead of writing a number down as it is, Alex first shifts it one place to the left (that is, he multiplies it by 10) and adds the shifted value to the original number. For example, for the number 123 he computes 1230 + 123 = 1353.

To make the disguised value look like an ordinary phone number, he then truncates it from the left so that it has exactly as many digits as the original number. In the example above he keeps only the last three digits and writes 353 in place of 123.

Given the disguised value that Alex wrote down, recover the original phone number. Because the entries may be corrupted, it is possible that no original number could have produced the written value. In that case, print IMPOSSIBLE.

Input

The input contains one or more test cases, each on its own line. Every test case is a single positive integer with fewer than 1,000,000 digits — the value written in the phone book.

The input ends with a line containing a single 0, which is not part of the data and must not be processed.

Output

For each test case, print one line in the following format:

k. result

where k is the test case number (starting from 1), the period is followed by a single space, and result is either the recovered original phone number or the word IMPOSSIBLE if it cannot be recovered.

Examples1

  1. Example 1

    Input
    353
    9988
    123456
    0
    
    Expected output
    1. 123
    2. IMPOSSIBLE
    3. 738496