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 SS consisting of lowercase latin letters 'aa' & 'bb' 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 ( SiS_i & Si+1S_{i+1} are adjacent characters) from String SS

  1. If chosen characters are "aaaa" then replace them with character 'aa'.
  2. If chosen characters are "bbbb" then replace them with character 'bb'.
  3. If chosen characters are "abab" then replace them with character 'bb'.

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

aaab undefined(applying 1st operation) \xrightarrow{\text{(applying 1st operation) }} aab undefined(applying 1st operation) \xrightarrow{\text{(applying 1st operation) }} ab undefined(applying 2nd operation) \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 TT (1T104)(1 \leq T \leq 10^4) , the number of test cases.

The next TT lines contain a string SS (1S105)(1 \leq \left|S\right| \leq 10^5) , S\left|S\right| denotes the size of the string. Each string SS will consist of characters 'aa' and 'bb'.

It is guaranteed that the sum of S\left|S\right| over all testcases doesn't exceed 10510^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 undefined(applying 1st operation) \xrightarrow{\text{(applying 1st operation) }} a .

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

Discussion

Statistics


73% Solution Ratio

Alamin_1804084Earliest, 8M ago

H_shafia4Fastest, 0.0s

zihad1783Lightest, 0 B

bokaifShortest, 114B

Submit

Login to submit

Editorial

Lets convert all 'ababab' to 'bbbbbb' as they can be minimized to 'bbb'. Then as a result we will ge...

Toph uses cookies. By continuing you agree to our Cookie Policy.