Run-Length Encoding

You are given an integer T representing the number of test cases. For each test case, you are given a string s consisting only of uppercase and lowercase English letters.

Your task is to compress each string using run-length encoding. In run-length encoding, consecutive groups of the same character are replaced by the character followed by the group length. For example, the string aaabbc should be encoded as a3b2c1.

Note: If the string is empty, output an empty string.

Example:

Input:
1
aaabbc
Output:
a3b2c1

</p>

inputFormat

The first line of input contains an integer T, the number of test cases. Each of the following T lines contains a single string s composed only of uppercase and lowercase letters.

Input is given via standard input (stdin).

outputFormat

For each test case, output the run-length encoded string on a separate line to standard output (stdout).

## sample

1
aaabbc

a3b2c1

</p>