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$ –

If chosen characters are "$aa$" then replace them with character '$a$'.

If chosen characters are "$bb$" then replace them with character '$b$'.

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) —

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

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 .