Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2571
Big String Outspread

Time Limit: 2 Seconds      Memory Limit: 65536 KB

When people are developing a Spin CAD (Computer aided design) system, they always face a problem that how to arrange the yarns more effectively.

The description of this problem is:

Usually, the kind of staple yarns will less than 25; so, we can use lowercase letters to indicate the 25 different kinds of yarns, for example, "abc"-means three yarns arrangement. Repetition of the yarns arrangement can be express with numbers and brackets , as , "2(abc)" means "abcabc" , "1(a)" = "1a" means "a"��"2ab"means "aab"; if there's no number for repetition before the brackets, we can assume that the number "1" has been bypassed, e.g. "cd(abc)" = "cd1(abc)" = "cdabc" ; This method is so simple and easy to understand as you see, but this great idea cannot be recognized by the poor computer. So, we got a task that we must unfold the expression into a status that the computer can understand it. Then, an ACM team takes this task, and you, are right an excellent guy in this team, and your task was described above.

Here are some hints for you to simplify this task:

The length of the original compact expression input will never exceed 250 characters, and the value of the number before the brackets which means the repetition of the letters will always less than 1000. And in the all expressions, there will be only some numbers, brackets, and letters in lowercased, also all the brackets will always be suited. (Exceptions in this section have been processed by other ACM guys).


Input

There's multi-cases of input data, the first line is a number N indicate the number of the cases. Then, N lines following give the N expressions which base on the description above.


Output

To each case input, output a unfolded expression in an independent line.


Sample Input

2
1(1a2b1(ab)1c)
3(ab2(4ab))

Sample Output

abbabc
abaaaabaaaababaaaabaaaababaaaabaaaab


Author: CAI, Minglun
Source: ZOJ Monthly, October 2005
Submit    Status