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$ –
$aa$" then replace them with character '$a$'.$bb$" then replace them with character '$b$'.$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.
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$ .
For each test case, print the minimum length string which can be gained after applying the operations.
| Input | Output |
|---|---|
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 .