SPOJ in Gyumri

  What's the next number in the following sequence?

1, 11, 21, 1211, 111221, ...

   Most people assume that the sequence has something to do with numeric values and struggle to find a pattern . In fact, the rule for generating the next value in the series is that each value is a description of the previous value. For example, 21 can be described as "one 2, one 1", leading to the next value of 1211. By this rule, the answer to the problem above is 312211 ("three 1, two 2, one 1").

   The process can also be reversed to determine previous values in the sequence. For example, the value that comes before 2221 (two 2, two 1) would be 2211, and the value before that would be 221. However, not every value has a previous value. For example, 221 has no previous value because it isn't a valid description, and 2212 has no previous value because the value it describes (222) would have a next value of 32, not 2212.

   The "primordial value" of some value is defined as the value that would generate a sequence containing the given value but that itself has no previous value. For example, if the starting value is 2221 the primordial value is 221, and if the starting value is 312211 the primordial value is 1. As a special case, the value 22 (for which the previous value would also be 22) is considered primordial.

   Your task is to write a program that determines primordial values for given starting values.

Input

   Input will consist of specifications for a series of tests. Information for each test is a single line containing a string of digits of length 1 <= n < 100 that specifies the last value in a sequence defined as above. A line containing the value 0 terminates the input.

Output

   Output should consist of one line for each test comprising the test number (formatted as shown) followed by a single space and the primordial value of the input value.

Examples