310906: CF1907B. YetnotherrokenKeoard

B. YetnotherrokenKeoardtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Polycarp has a problem — his laptop keyboard is broken.

Now, when he presses the 'b' key, it acts like an unusual backspace: it deletes the last (rightmost) lowercase letter in the typed string. If there are no lowercase letters in the typed string, then the press is completely ignored.

Similarly, when he presses the 'B' key, it deletes the last (rightmost) uppercase letter in the typed string. If there are no uppercase letters in the typed string, then the press is completely ignored.

In both cases, the letters 'b' and 'B' are not added to the typed string when these keys are pressed.

Consider an example where the sequence of key presses was "ARaBbbitBaby". In this case, the typed string will change as follows: "" $\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".

Given a sequence of pressed keys, output the typed string after processing all key presses.

Input

The first line of the input data contains an integer $t$ ($1 \le t \le 1000$), the number of test cases in the test.

The following contains $t$ non-empty lines, which consist of lowercase and uppercase letters of the Latin alphabet.

It is guaranteed that each line contains at least one letter and the sum of the lengths of the lines does not exceed $10^6$.

Output

For each test case, output the result of processing the key presses on a separate line. If the typed string is empty, then output an empty line.

ExampleInput

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

Output

ity
YetnotherrokenKeoard
le
Imprle
revile

usyasaeeinaedofloominglossoms
CDARIES
codeforces
es

helaoard

题目大意：
Polycarp的笔记本电脑键盘坏了。现在，当他按下“b”键时，它删除了已输入字符串中的最后一个（最右边的）小写字母。如果已输入的字符串中没有小写字母，那么这次按键将被完全忽略。同样地，当他按下“B”键时，它删除了已输入字符串中的最后一个（最右边的）大写字母。如果已输入的字符串中没有大写字母，那么这次按键也将被完全忽略。在这两种情况下，按下“b”和“B”键时，这些键本身不会添加到已输入的字符串中。

输入输出数据格式：
输入数据的第一行包含一个整数t（1≤t≤1000），表示测试用例的数量。接下来t行包含由拉丁字母的小写和大写字母组成的非空行。保证每行至少包含一个字母，且所有行的长度之和不超过10^6。

对于每个测试用例，输出处理完所有按键后的已输入字符串。如果已输入的字符串为空，则输出一个空行。题目大意： Polycarp的笔记本电脑键盘坏了。现在，当他按下“b”键时，它删除了已输入字符串中的最后一个（最右边的）小写字母。如果已输入的字符串中没有小写字母，那么这次按键将被完全忽略。同样地，当他按下“B”键时，它删除了已输入字符串中的最后一个（最右边的）大写字母。如果已输入的字符串中没有大写字母，那么这次按键也将被完全忽略。在这两种情况下，按下“b”和“B”键时，这些键本身不会添加到已输入的字符串中。 输入输出数据格式： 输入数据的第一行包含一个整数t（1≤t≤1000），表示测试用例的数量。接下来t行包含由拉丁字母的小写和大写字母组成的非空行。保证每行至少包含一个字母，且所有行的长度之和不超过10^6。 对于每个测试用例，输出处理完所有按键后的已输入字符串。如果已输入的字符串为空，则输出一个空行。