题目描述

算术表达式通常采用中缀表示法，即运算符位于两个操作数之间。例如，$(x + y) * (z - w)$ 就是一个中缀表示法的算术表达式。然而，如果表达式采用后缀表示法（也称为逆波兰表示法），则更容易编写程序来求值。在后缀表示法中，运算符位于其两个操作数之后，而这两个操作数本身也可以是表达式。例如，$x\ y\ +\ z\ w\ -\ *$ 就是上述算术表达式的后缀表示法。注意，此时不再需要括号。

为了求解后缀表示法的表达式，可以使用基于栈的算法。栈是一种支持以下两种操作的数据结构：

• push：将一个数字压入栈顶。
• pop：从栈顶弹出一个数字。

在求解过程中，我们从左到右处理表达式。如果遇到数字，则将其压入栈中；如果遇到运算符，则从栈中弹出前两个数字，对它们进行运算，并将结果重新压入栈中。具体来说，以下伪代码展示了遇到运算符 $O$ 时的处理方式：

$a := \text{pop}();$  
$b := \text{pop}();$  
$\text{push}(b\ O\ a);$  

最终，栈中剩下的唯一数字就是表达式的结果。

现在，假设我们使用队列而非栈。队列也有 push 和 pop 操作，但它们的含义不同：

• push：将一个数字插入队列的末尾。
• pop：从队列的前端取出一个数字。

问题：能否重新编写给定的表达式，使得使用队列的算法结果与使用栈的原始表达式结果相同？

输入格式

第一行包含一个整数 $T$（$T \leq 200$）。接下来的 $T$ 行，每行给出一个后缀表示法的表达式。算术运算符用大写字母表示，数字用小写字母表示。保证每个表达式的长度不超过 $10000$ 个字符。

输出格式

对于每个给定的表达式，输出一个表达式，使得使用队列的算法结果与原始表达式使用栈的算法结果相同。为了保证解的唯一性，不允许假设运算符具有结合性或交换性。

样例输入 1

2  
xyPzwIM  
abcABdefgCDEF  

样例输出 1

wzyxIPM  
gfCecbDdAaEBF  

来源

Ulm Local 2007