Description

When chatting with friends, repeating the same character wastes data! Compress consecutive identical characters into 'character+count' format. However, if the compressed length is not shorter, return the original.

Input

Output

Constraints

• •1 <= string length <= 1000
• •Only lowercase letters

Examples

"aabcccde"

"a2b1c3d1e1"

"aaaaaaaaaa"

"a10"