SP17504 RLE - Run length encoding

Ram had to send large amount of data to his friend Vishnu. Since he was concerned about the time and the amount of data transfer it will take, he wanted to compress the data before he sent it. So he turns to you for help. You need to perform run length encoding on a given string. The encoding is as follows : 'consecutive character count' followed by '!' followed by the 'character'. Do not encode the characters unless they lead to compression !

Input consists of multiple lines of strings s, one string per line, with |s|

For each input string, output a single line printing the run length encoding of the input string