Nesting Depth

tl;dr: Given a string of digits S, insert a minimum number of opening and closing parentheses so that the result is balanced and each digit d is inside exactly d matching pairs of parentheses.

The nesting of two parentheses is the substring strictly between them. An opening parenthesis and a closing parenthesis to its right match if their nesting is empty, or if every parenthesis in their nesting matches another parenthesis in that nesting. The nesting depth of a position p is the number of matching pairs m such that p lies inside the nesting of m.

For example, in 0((2)1), (((3))1(2)), ((((4)))), and ((2))((2))(1), every digit equals its nesting depth. The first three have minimum length among strings with the same digits in the same order. The last one does not, because ((22)1) also has the digits 221 and is shorter.

Given S, find a string S' made of parentheses and digits such that:

• every parenthesis in S' matches some other parenthesis,
• removing all parentheses from S' leaves S,
• each digit in S' equals its nesting depth, and
• S' has minimum length.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one string S.

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1 and y is the string S' defined above.

1 ≤ T ≤ 100

1 ≤ length of S ≤ 100

The strings ()0000(), (1)0(((()))1), and (1)(11)000 are not valid answers to Sample 1, 2, and 3, respectively, only because they are not of minimum length. The strings 1)( and )(1 are not valid answers to Sample 4 because they contain unmatched parentheses, and the nesting depth is 0 at the position where there is a 1.