InternDoor

Write each run of letters once

Easystrings · two pointersRead the input, print the output

Reported in interviews at (where)

A run is a stretch of the same letter, side by side, that cannot be made longer. Squeeze a string by writing every run of 2 or more letters as the letter followed by the run's length. A letter that stands alone stays as it is.

For each string, print it squeezed.

Input

The first line holds T, the number of tests. Each test is one line holding one string of lowercase letters.

Output

For each test, one line: its string, squeezed.

Example
Input
4
aaabccddd
xyz
aabaa
qqqqqqqqqqqq
Output
a3bc2d3
xyz
a2ba2
q12
  1. The runs of a, c and d become the letter and its length; the lone b stays as it is.
  2. No letter sits next to itself, so nothing changes.
  3. Only letters side by side make a run: the two runs of a are written apart.
  4. A long run gives a length of more than one digit.

Limits

  • 1 <= T <= 100
  • each string holds 1 to 100000 letters
  • all the strings together hold at most 400000 letters

Hints

Hint 1

Walk the string with two positions: the start of a run, and the first letter after it.

Hint 2

Building the answer by adding to a string one piece at a time can be slow in some languages: collect the pieces and join them once.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.