题目描述

Polycarp 遇到了一个问题——他的笔记本电脑键盘坏了。

现在，当他按下小写字母 'b' 键时，它会像一种特殊的退格键一样：删除已经输入字符串中最后（最右边）的一个小写字母。如果输入的字符串中没有小写字母，那么这个按键会被完全忽略。

类似地，当他按下大写字母 'B' 键时，它会删除已经输入字符串中最后（最右边）的一个大写字母。如果输入的字符串中没有大写字母，那么这个按键会被完全忽略。

在这两种情况下，按下 'b' 或 'B' 键时，这两个字母都不会被添加到输入字符串中。

举个例子，按键序列为 "ARaBbbitBaby"。此时，输入字符串的变化如下："" $\xrightarrow{\texttt{A}}$ "A" $\xrightarrow{\texttt{R}}$ "AR" $\xrightarrow{\texttt{a}}$ "ARa" $\xrightarrow{\texttt{B}}$ "Aa" $\xrightarrow{\texttt{b}}$ "A" $\xrightarrow{\texttt{b}}$ "A" $\xrightarrow{\texttt{i}}$ "Ai" $\xrightarrow{\texttt{t}}$ "Ait" $\xrightarrow{\texttt{B}}$ "it" $\xrightarrow{\texttt{a}}$ "ita" $\xrightarrow{\texttt{b}}$ "it" $\xrightarrow{\texttt{y}}$ "ity"。

给定一系列按键序列，请输出每个序列处理完所有按键后的最终输入字符串。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

接下来有 $t$ 行，每行是一个非空字符串，仅包含拉丁字母的大小写字母。

保证每行至少包含一个字母，且所有行的总长度不超过 $10^6$。

输出格式

对于每个测试用例，输出处理完所有按键后的结果字符串，各占一行。如果结果字符串为空，则输出一个空行。

说明/提示

由 ChatGPT 4.1 翻译

样例

12
ARaBbbitBaby
YetAnotherBrokenKeyboard
Bubble
Improbable
abbreviable
BbBB
BusyasaBeeinaBedofBloomingBlossoms
CoDEBARbIES
codeforces
bobebobbes
b
TheBBlackbboard

ity
YetnotherrokenKeoard
le
Imprle
revile

usyasaeeinaedofloominglossoms
CDARIES
codeforces
es

helaoard