Description

Natsuzora 老师正在带小朋友们排队。小朋友们有三种性格，分别用 a、b 和 c 表示。小朋友们排成一队，他们的性格形成了一个字符串 $S$（下标从 $0$ 开始）。

在长期的观察中，Natsuzora 发现了一个规律：如果一个队列中连续三个小朋友的性格互不相同（如 abc、acb、bac 等），那么这三个小朋友会交头接耳。Natsuzora 非常讨厌交头接耳的小朋友，所以他需要保证队列中不会出现这种情况。

具体地，Natsuzora 的操作如下（其中 $|S|$ 表示字符串 $S$ 的长度）：

1. 若 $|S|<3$，不进行任何操作并退出。
2. 开始本轮检查，并初始化 $i=0$。
3. 检查第 $i$、$i+1$ 和 $i+2$ 个小朋友的性格是否互不相同。若是，则踢出第 $i+1$ 个小朋友（将第 $i+1$ 个字符删除）；否则，令 $i:=i+1$。
4. 此时，若 $i+2\ge |S|$，回忆本轮检查是否有踢出过小朋友。若有踢出过，回到 1；若没有踢出过，说明已经没有小朋友会交头接耳，退出循环。
5. 若 $i+2<|S|$，回到 3。

作为班长，你需要帮助 Natsuzora 完成上述操作，并输出最终的字符串。

Input

本题包含多组数据。

第一行一个整数 $T$（$1\leq T\leq 10^4$），表示数据组数。

对于每组数据，输入一行一个字符串 $S$（$2\leq |S|\leq 10^6$），表示小朋友排成的队列。

数据保证 $\sum |S|\le 10^6$，且 $S$ 中仅包含 a、b、c 三种字符。

Output

对于每组数据，输出一行一个字符串，表示操作完成后的队列。

Samples

3
ab
acbcabab
abababac

ab
ab
ac

Note

此处是第二个样例的解释。

在第一轮，字符串会发生如下变化：

$$\begin{aligned} &\downarrow\\ &[a{\color{red}c}b]cabab \end{aligned} $$$$\begin{aligned} &\downarrow\\ &[a{\color{red}b}c]abab \end{aligned} $$$$\begin{aligned} &\downarrow\\ &[aca]bab \end{aligned} $$$$\begin{aligned} &\downarrow\\ a&[c{\color{red}a}b]ab \end{aligned} $$$$\begin{aligned} &\downarrow\\ a&[c{\color{red}b}a]b \end{aligned} $$$$\begin{aligned} &\downarrow\\ a&[c{\color{red}a}b] \end{aligned} $$$$\begin{aligned} &\downarrow\\ a&[cb\text{ }] \end{aligned} $$

在第二轮，字符串会发生如下变化：

$$\begin{aligned} &\downarrow\\ &[a{\color{red}c}b] \end{aligned} $$$$\begin{aligned} &\downarrow\\ &[ab\text{ }] \end{aligned} $$

因此，ab 是最终的字符串。

Resources

The 22nd UESTC Programming Contest Preliminary