Problem Description

PepperLa loves strings.His desire for strings is infinite, but his storage is limited.

There is a method to compress strings. A substring whose characters are all the same and are all lower case letters could be compressed into one character plus one hexadecimal number which represents character's counting. (numbers over ten are represented in upper case letters) Here a substring is a string could be obtained by deleting several characters from the begin and end.

For example,the string is "aaacccccccccc". compression operations could replace "aaa" with "a3", and repalce "cccccccccc" with "cA". So the compressed string becomes "a3cA". If you choose 16 'a', you could compress it to "a10", and if you choose 17 'a', you could compress it to "a11", but you can't compress "11" to "12".

The method allows lossy compression which means you can miss at most 1 character before you compressing the string. It should be noted that after deleting one character the string is actually not successive.(See sample testcase for details)

You can do any times or even zero times of compression operations, find the shortest compressed string, if there are multiple answers, output the one with minimal lexicographic order.

Input

There are multiple test cases in this problem.

For every test case, the input contains one line, the given string.

The input guarantees that strings contains only lower case letters

For each test case, $1 < string.length \leq 10^6$, $\sum{length}\leq 5 \times 10^6$

Output

For each test case, output a single line contains the answer string.

aaacccccccccc
aaabaaa

a2cA
a3a3

Hint

In first string, if you choose to miss one 'a', the string becomes "aacccccccccc" and compressed string is "a2cA".

In second string, if you choose to miss one 'b', the string becomes something like "aaa aaa" the answer is not "a6" but "a3a3".