중첩 깊이

tl;dr: 숫자로 이루어진 문자열 S가 주어진다. 괄호를 최소 개수로 끼워 넣어서 결과 문자열이 균형을 이루고, 각 숫자 d가 정확히 d쌍의 짝이 맞는 괄호 안에 놓이게 하라.

두 괄호의 중첩은 두 괄호 사이에 있는 부분 문자열이다. 여는 괄호와 그보다 오른쪽에 있는 닫는 괄호는, 중첩이 비어 있거나 중첩 안의 모든 괄호가 중첩 안의 다른 괄호와 짝을 이루면 짝이 맞는다고 한다. 위치 p의 중첩 깊이는 p가 중첩 안에 포함되는 짝 맞는 괄호 쌍의 개수 m이다.

예를 들어 0((2)1), (((3))1(2)), ((((4)))), ((2))((2))(1)에서는 모든 숫자가 중첩 깊이와 같다. 앞의 세 문자열은 같은 숫자를 같은 순서로 갖는 문자열 중 길이가 가장 짧다. 마지막 문자열은 ((22)1)도 숫자 221을 갖고 더 짧으므로 최소가 아니다.

S가 주어질 때, 괄호와 숫자로 이루어진 문자열 S'를 찾아라. S'는 다음 조건을 만족해야 한다.

• S'의 모든 괄호는 다른 괄호와 짝을 이룬다.
• S'에서 괄호를 모두 지우면 S가 된다.
• S'의 각 숫자는 그 위치의 중첩 깊이와 같다.
• S'의 길이가 최소다.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 이어서 $T$개의 줄에 각각 문자열 S가 한 개씩 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 정의한 S'이다.

1 ≤ T ≤ 100

1 ≤ S의 길이 ≤ 100

()0000(), (1)0(((()))1), (1)(11)000은 각각 샘플 1, 2, 3의 유효한 답이 아니다. 이유는 길이가 최소가 아니기 때문뿐이다. 1)(과 )(1은 샘플 4의 유효한 답이 아니다. 짝이 맞지 않는 괄호가 있고, 1이 있는 위치에서 중첩 깊이가 0이기 때문이다.