在本题中，我们考虑由小写拉丁字母 “a”、“b” 和 “c” 组成的字符串。
对于本题，我们按如下方式递归定义正则表达式：
- 单个字符 “$” 是一个接受空字符串的正则表达式。
- 单个字符 “a”、“b” 和 “c” 分别是接受字符串 “a”、“b” 和 “c” 的正则表达式。
- 如果 $P$ 是一个正则表达式，则 “(P)” 也是一个正则表达式，它接受所有被 $P$ 接受的字符串。
- 如果 $P$ 是通过应用规则 1–4 中任意一条直接得到的正则表达式，则其迭代（记为 “$P*$”）也是一个正则表达式，它接受形式为 $s = u_1u_2 \dots u_k$（零个或多个字符串的拼接）的字符串，其中 $k$ 为任意非负整数，且每个字符串 $u_i$ 均被 $P$ 接受。
- 如果 $P$ 和 $Q$ 是通过应用规则 1–5 中任意一条直接得到的正则表达式，则它们的拼接（简记为 “$PQ$”）也是一个正则表达式，它接受形式为 $s = uv$（$u$ 和 $v$ 的拼接，两者均可为空）的字符串，其中前缀 $u$ 被 $P$ 接受，后缀 $v$ 被 $Q$ 接受。
- 如果 $P$ 和 $Q$ 是通过应用规则 1–6 中任意一条直接得到的正则表达式，则它们的并（记为 “$P|Q$”）也是一个正则表达式，它接受所有被 $P$ 接受的字符串以及所有被 $Q$ 接受的字符串。
规则 4–6 中的限制旨在防止歧义并确定运算优先级：在读取正则表达式时，先计算迭代，再计算拼接，最后计算并。括号在确定括号内运算的优先级方面起常规作用。例如，正则表达式 “a(bac|ac*)” 被解读为 “接受 a，随后是（b 接着 a 接着 c）或（a 接着零个或多个 c）”。
给定一个正则表达式 $r$，求该正则表达式 $r$ 所接受的最短字符串 $s$。如果存在多个这样的字符串，则求字典序最小的一个。
输入格式
输入的第一行包含一个整数 $T$，表示测试用例的数量（$1 \le T \le 300$）。 接下来的 $T$ 行，每行描述一个测试用例。每个测试用例包含一个由上述规则构造的正则表达式 $r$。其长度在 1 到 300 个字符之间。 所有正则表达式的长度之和不超过 300。
输出格式
对于每个测试用例，输出一行，包含该正则表达式 $r$ 所接受的最短字符串。如果存在多个这样的字符串，则输出字典序最小的一个。 如果答案为空字符串，则输出单个字符 “$”。
样例
样例输入 1
3 a ab|ac*(ca|cb) ((ab|ac)a)*
样例输出 1
a ab $