Cellphone Text Compression

Interview

Time limit1sMemory limit512 MB

Summary

For each of N strings, output its run-length encoding: each maximal run of identical characters as a count followed by the character.

Level: Easy3 of 10
Topics: String, Implementation, Simulation
Solved: No attempts yet

Problem

Your new cellphone plan charges you for every character you send. Since you tend to send messages made of sequences of symbols, you came up with the following compression technique: for each symbol, write the number of times it appears consecutively, followed by the symbol itself. This technique is called run-length encoding.

More formally, a block is a substring of identical symbols that is as long as possible. A block is represented in compressed form as the length of the block followed by the symbol in that block. The encoding of a string is the representation of each block in the string, in the order in which the blocks appear in the string.

Given a string, write a program to encode it in this format.

Input

The first line contains the number N, the number of lines that follow. Each of the next N lines contains at least one and at most 80 characters, none of which are spaces.

Output

Output N lines. Line i is the encoding of line i+1 of the input. The encoding of a line is a sequence of pairs separated by a space, where each pair is an integer (the number of times the character appears consecutively), a space, and the character.

Examples1

Example 1

Input

4
+++===!!!!
777777......TTTTTTTTTTTT
(AABBC)
3.1415555

Expected output

3 + 3 = 4 !
6 7 6 . 12 T
1 ( 2 A 2 B 1 C 1 )
1 3 1 . 1 1 1 4 1 1 4 5