Look and Say

Interview

Time limit1sMemory limit128 MB

Summary
For each input string of digits, produce the next look-and-say element by counting runs of equal digits and writing each count followed by the digit.
Level

Easy3 of 10

Topics
String, Implementation
Solved
No attempts yet

Problem

The look-and-say sequence is defined as follows. Start with any string of digits as the first element of the sequence. Each subsequent element is obtained by "reading aloud" the previous element. For example, the string 122344111 can be described as "one 1, two 2's, one 3, two 4's, three 1's". Therefore the element that follows 122344111 is 1122132431. Similarly, 101 follows 1111111111 (ten 1's). Note that the previous element cannot in general be recovered uniquely: for instance, a string of 112213243 consecutive 1's also produces 1122132431 as its next element.

Input

The input consists of several test cases. The first line contains the number of test cases. Each test case is a single line of up to 1000 digits.

Output

For each test case, print on its own line the element that follows the given string.

Examples1

  1. Example 1

    Input
    3
122344111
1111111111
12345
    Expected output
    1122132431
101
1112131415