Message Compression

Version: Phuoc Hung OJ Extended

Problem Statement

A message is represented by a string $S$ containing only uppercase English letters from A to Z.

Compress each maximal run of equal consecutive characters as follows:

• A run of length $1$ is kept as the character itself.
• If a character $c$ appears consecutively $k$ times with $k \ge 2$, replace the run by $c$ followed by the decimal representation of $k$.

For example, AAABBCCCCDAA becomes A3B2C4DA2.

Construct the compressed string $T$ and determine its length $|T|$.

Input

One line contains the string $S$.

Output

• The first line contains the compressed string $T$.
• The second line contains the integer $|T|$.

Subtasks

• Subtask 1 (40%): $1 \le |S| \le 255$.
• Subtask 2 (30%): $1 \le |S| \le 10^5$.
• Subtask 3 (30%): $1 \le |S| \le 10^6$.

Examples

Example 1

Input

AAABBCCCCDAA

Output

A3B2C4DA2
9

Explanation

The runs are AAA, BB, CCCC, D, AA, with lengths $3,2,4,1,2$. They become A3, B2, C4, D, A2.

Example 2

Input

ABCDE

Output

ABCDE
5

Explanation

Every run has length $1$, so the string is unchanged.

Example 3

Input

AAAAAAAAAAAA

Output

A12
3

Explanation

There are $12$ consecutive A characters, so the run is represented by A12, whose length is $3$.