Look and Say

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.

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.

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