Run-Length Encoding

Given a string s, your task is to perform run-length encoding on it. In run-length encoding, consecutive occurrences of the same character are replaced by the count of occurrences followed by the character. For example, if s = "aaabccddd", then its run-length encoding is "3a1b2c3d".

The encoding process can be formally described as follows: if the input string is \( s = s_1 s_2 \ldots s_n \), then you need to form groups of consecutive identical characters and output the count and the character for each group.

Note that if the string is empty, the output should also be an empty string.

Examples:

• Input: "aaabccddd" Output: "3a1b2c3d"
• Input: "a" Output: "1a"
• Input: "abcdef" Output: "1a1b1c1d1e1f"
• Input: "aaabbbbcccdde" Output: "3a4b3c2d1e"
• Input: "ababab" Output: "1a1b1a1b1a1b"

inputFormat

The input consists of a single line containing the string s for which you must compute the run-length encoding. The string may consist of lowercase English letters.

Input Format:

s

outputFormat

Output a single line containing the run-length encoding of the input string.

Output Format:

encoded_string

## sample

aaabccddd

3a1b2c3d