# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Compressed String

By Ishtiaq · Limits 1s, 512 MB

You are given a string $S$ consisting of lowercase latin letters '$a$' & '$b$' only. Your task is to minimize the size of the string by applying the following three operations as many times as you wish. At a time, you can apply only one operation.

Choose two adjacent characters ( $S_i$ & $S_{i+1}$ are adjacent characters) from String $S$

1. If chosen characters are "$aa$" then replace them with character '$a$'.
2. If chosen characters are "$bb$" then replace them with character '$b$'.
3. If chosen characters are "$ab$" then replace them with character '$b$'.

For example, $S =$ "aaab". So, we can do the following operations (chosen characters are underlined) —

aaab $\xrightarrow{\text{(applying 1st operation) }}$ aab $\xrightarrow{\text{(applying 1st operation) }}$ ab $\xrightarrow{\text{(applying 2nd operation) }}$ b

We cannot minimize it more by applying any of the operations.

So, you have to find the minimum length string that can be gained after applying the operations.

## Input

The first line contains an integer $T$ $(1 \leq T \leq 10^4)$ , the number of test cases.

The next $T$ lines contain a string $S$ $(1 \leq \left|S\right| \leq 10^5)$ , $\left|S\right|$ denotes the size of the string. Each string $S$ will consist of characters '$a$' and '$b$'.

It is guaranteed that the sum of $\left|S\right|$ over all testcases doesn't exceed $10^5$ .

## Output

For each test case, print the minimum length string which can be gained after applying the operations.

## Sample

InputOutput
3
aa
aaab
bbbb

a
b
b


For the first test case, aa $\xrightarrow{\text{(applying 1st operation) }}$ a .

For the third test case, bbbb $\xrightarrow{\text{(applying 3rd operation) }}$ bbb $\xrightarrow{\text{(applying 3rd operation) }}$ bb $\xrightarrow{\text{(applying 3rd operation) }}$ b .

### Statistics

74% Solution Ratio

Alamin_1804084Earliest, 1M ago

kazol196295Fastest, 0.0s

mah20tShortest, 174B