Run-Length Encoding

Given a string, perform run-length encoding. In run-length encoding, consecutive occurrences of the same character are replaced by a single occurrence of the character followed by the number of times it appears. For example, the string aaabcc is encoded as a3b1c2.

The encoding process can be formally described by the formula: (output = \bigoplus_{i=1}^n (s_i ; \text{concatenated with count of its consecutive occurrences})), where (\bigoplus) represents string concatenation. If the input string is empty, output an empty string.

inputFormat

The first line of input contains a single integer (T) ((1 \le T \le 100)), representing the number of test cases. Each of the next (T) lines contains a non-empty string consisting of lowercase letters.

outputFormat

For each test case, output a single line containing the run-length encoded string corresponding to the input string.## sample

4
aaabccdddda
zzzzyyyx
aabbcc
abcde

a3b1c2d4a1
z4y3x1
a2b2c2
a1b1c1d1e1