Limits 1s, 512 MB

Lily wants to build a beautiful string. She has been adding alphabets together to make this string.

She realized the string was growing heavy with too many alphabets and decided to replace every consecutive identical alphabet except the first occurrence of that alphabet with “#”.

As a little girl, she doesn't care about the case sensitivity of the characters. The weight of the uppercase and the lowercase of an alphabet are the same.

Can you help her by writing a program to do this?

Input

The first line of the input file will contain a single integer TT (1T1051 \le T \le 10^5) indicating how many test cases that your program will have to process. Each test case will contain a string SS, containing lowercase or uppercase English alphabets. The length of SS is not greater than 10510^5.

Output

For each test case, print the string with all consecutive alphabets replaced with “#” leaving only the first occurrence unchanged.

Sample

InputOutput
2
aabbccdd
aaabbbaaa
a#b#c#d#
a##b##a##

Submit

Login to submit.

Statistics

85% Solution Ratio
PromiseIUBEarliest, Jul '17
Black_mambaFastest, 0.0s
Riz1ahmedLightest, 262 kB
SabbasachiSutradharShortest, 124B
Toph uses cookies. By continuing you agree to our Cookie Policy.