Helen has come up with a way to shorten the length of the messages send to their counterparts in the past. Helen considers only individual words, and uses the following rules to define a "shortened word":

1. a single, lower-case letter is a compressed word
2. (e₁ e₂ ... e_t n) where t and n are non-negative integers and e_i is a compressed word.

You should observe that a compressed word of one character is the same as an uncompressed word. To uncompress the compressed word (e₁ e₂ ... e_t n) we uncompress each e_i, concatenate those uncompressed words into a new word, and repeatedly concatenate that word n times. For example:

• a would be uncompressed as a,
• (a 3) would be uncompressed as aaa,
• (a (b c d 2) 3) would be uncompressed as abcdbcdabcdbcdabcdbcd.

Write a program to uncompress a compressed word.

Input

First line T, the number of test cases (=12). Next T lines contain correctly formed compressed words.

Output

For each case print in a new line the uncompressed word without spaces.

Constraints

0 < n <= 10000, 1 <= t <= 26

length of expressions will be less than 100, and the compressed worf will consist of latters (a-z), numbers and brackets.

Note: There may or may not be more than one space between brackets and letters or number. For example ( a ), (a3), ( a 3 ) are all correct expressions.

Example

Input:
3
a
( a 3 )
( a ( b c d 2 ) 3 )

Output:
a
aaa
abcdbcdabcdbcdabcdbcd