王国の諜報機関は独特の暗号化方式を使っており，英小文字のみからなる空でない文字列である通信文を，以下の BNF で記述される文法に従う式 <expr> に暗号化する．

<expr>	::=	<char> | <expr><expr> | ?(<expr>)
<char>	::=	a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

暗号化前の通信文は，以下に述べる手順を暗号文に適用した結果としてあり得る文字列のうち，辞書式順序で最初に現れるものである．

手順: 式中に ? が残っている限り，以下の操作を繰り返す．

1. ?(s) という形の連続部分文字列であって，s に記号 ?, (, ) を含まないようなものの出現（式全体でもよい）を任意に 1 つ選ぶ．
2. s が空文字列であれば，選んだ ?() の出現を単に取り除く．
3. そうでなければ，選んだ ?(s) の出現を，s の先頭または末尾 1 文字を取り除いた文字列で置き換える．

たとえば ?(?(icp)c) という式を考えてみよう．このとき，選べる出現は ?(icp) のみであり，この部分が cp または ic に置き換えられる．したがって，式全体は ?(cpc) または ?(icc) となる．さらに，それぞれの式全体を選んで置き換えると，結果としてあり得る文字列は pc, cp, cc, ic の 4 種類である．このうち，辞書式順序で最初に現れる cc が暗号化前の通信文である．

敵対する共和国の諜報員であるあなたは，暗号文，すなわち上述の式を入手することに成功した．暗号化前の通信文を求めよ．

入力は複数のデータセットからなる．入力の 1 行目はデータセットの個数 n のみからなり，n は 50 を超えない．続く n 行に，1 行に 1 つずつデータセットが与えられる．

データセットは問題文中の BNF で記述される文法に従う式 <expr> の 1 行のみからなり，式の文字数は記号を含めて 1000 を超えない．

各データセットについて，問題文中の手順を適用した結果としてあり得る文字列のうち，辞書式順序で最初に現れるものを 1 行に出力せよ．正しい出力は空文字列にならないことが保証される．

6
?(icpc)
?(?(icpc))
?(ic)?(pc)
?(?(icp)c)
?(i?(?(c))pc)
?(bca)?(?(bca))

cpc
cp
cc
cc
ip
bca