RUNLEN - Run Length Encoding

no tags 

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

hide comments
Francky: 2014-12-28 16:36:47

Please give the set of char used in input. Is it 'a..z', or 'A..Z' too, or more ???
==
You should give an example with "aaabba", is it "4a2b", or rather (I suppose) "3a2b1a" ?
edit : "consecutively" in description confirm that 2nd answer should be correct.

Last edit: 2014-12-28 19:15:33

Added by:Aswin Murugesh
Date:2014-12-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Source