Run-Length Encoding

Version: Phuoc Hung OJ Extended

Problem Statement

You are given a string $S$ consisting only of uppercase Latin letters from A to Z.

Split $S$ into maximal consecutive runs of equal characters. Encode each run by writing its character followed immediately by the number of occurrences in that run. The count must always be written, even when it is $1$.

Construct the encoded string.

Input

A single line containing $S$.

Output

Print the encoded representation of $S$.

Subtasks

• Subtask 1 (50 points): $1 \le |S| \le 10^3$.
• Subtask 2 (50 points): $1 \le |S| \le 10^6$.
• In every subtask, $S$ contains only A..Z.

Examples

Input

AAABCCCCDDDA

Output

A3B1C4D3A1

Explanation

The runs are AAA, B, CCCC, DDD, and A, with lengths $3,1,4,3,1$ respectively. Therefore they are encoded as A3, B1, C4, D3, and A1, producing A3B1C4D3A1.