BasicStrings10 points

Run-length squeeze for sensor strings

A warehouse scanner sends long strings in which the same letter repeats many times, for example AAAABBBCCD. To save bandwidth, the firmware compresses each string by replacing every run of identical consecutive letters by the letter followed by the length of the run.

The letters are case-sensitive (a and A are different). A run of length one is also written with its count, so AAAABBBCCD becomes A4B3C2D1.

Task: read one line containing 1 to 300 English letters and no spaces. Print the compressed string.

Sample tests

Input

AAAABBBCCD

Expected output

A4B3C2D1

Input

aAaA

Expected output

a1A1a1A1

Your answer is also checked against 3 hidden tests.