#1011 압축풀기

99  1 s   128 MB  

Description

문자열을 압축하는 가장 간단한 방법은 반복되는 부분문자열(substring)을 하나로 묶는것이다. 예를 들어 문자열 ABCABCABCABC와 같이 반복될 경우 이를 (3ABC)로 묶을 수 있다.

다시 말해서 부분문자열 XX...X 와 같이 $D$번 나타날 경우 (DX)로 압축을 할 수 있다. 연속된 부분 문자열은 최대 $9$회 반복이 가능하다고 가정하자.

이런 방법을 이용해서 문자열CABABABABABABCC(6AB)C, C(2(3AB))C로 압축할 수 있다. 압축된 문자열이 주어졌을 때, 원 문자열로 복원하는 프로그램을 구현하라.

Input

입력은 여러 개의 테스트 케이스로 구성된다. 입력의 첫 행에는 테스트 케이스의 수 $T$ 가 주어진다. $(1 \leq T \leq 300)$

테스트 케이스는 한줄에 하나의 문자열로 이뤄지며, 문자열은 대문자 알파벳, 그리고 숫자 $1$이상 $9$이하의 숫자와 문자, (, )로 이뤄져있다. 문자열의 최대 길이는 $50$자 이하다.

(DX)의 형태의 입력이 있을 경우 $D$는 반드시 $1$이상 $9$이하의 숫자이며, 문자열 X의 길이는 무조건 $1$이상이다.

Output

각 테스트 케이스의 순서대로 복원된 문자열을 한 줄에 하나씩 출력한다. 복원된 문자열의 길이는 $1,000$자 이하다.

Sample Input

Sample Output

5
C(6AB)C
C(2(3AB))C
CO(1N)TEST
(2(2AB))
AAAAAAAAAAAAAAAAAAAAA
CABABABABABABC
CABABABABABABC
CONTEST
ABABABAB
AAAAAAAAAAAAAAAAAAAAA

Source

2009 Ajou University Programming Contest