1470. Improve RLE

A computer programmer and mathematician Kumar Harikrishnan develops a new data compression system – ACM (Advanced Compression Method) – which will incorporate all of his brilliant ideas.

The first component of ACM will be a modification of well-known RLE algorithm, called Improved RLE. Since Kumar have much more difficult tasks to accomplish (such as to write Improved Hamming and Improved Lempel-Ziv), he asks you to implement this simple, yet important part of a system.

An algorithm should replace repeating substrings of source string with a single instance of substring concatenated with the number of repetitions. If some substring should not be repeated, it is concatenated with number 1.

Your program must find the shortest possible compression of the given string.

A single line of input file contains the string to be compressed. It may contain spaces, but does not contain digits as Kumar has invented a complex digit-escaping system to prevent uncompressing ambiguity.

Output file must contain minimal length compression of the source string. There should be no extra whitespace characters before or after the string.

Length of the source string is from 1 to 1000 characters.

aaaaaaaaaa

a10

a c c c

a1 c3

abc

abc1