Decode Repeated Groups

Decode lowercase letters and (substring){k} repeat groups, with nesting and k=0 allowed.

See "Input" for the standard input/output conventions and constraints added by this site.

输入格式

q lines of encoded strings; this site adds that each string and its decoded length are ≤200000, with depth ≤1000.

输出格式

Output each decoded string on its own line.

样例 1

输入：

3
abs(cs){3}g
a(b(c){2}){2}
x(yz){0}q

输出：

abscscscsg
abccbcc
xq

样例 2

输入：

1
a(b){0}c

输出：

ac

样例 3

输入：

1
(ab){2}

输出：

abab