Given a string, compress the string using the run length encoding mechanism.

Run length encoding allows compression of strings by making note of the number of times they occurred consecutively.

For example, aaabbccc is encoded as 3a2b3c.

Input

First line of the input consists of a number t, denoting the number of test cases.

Each test case contains a string s, with length <= 100.

Output

Output the compressed string for each test case.

Example

Input:
1
aaabbb

Output:
3a3b