Let there be a parenthesis sequence string . This sequence is not guaranteed to be balanced. Your task is to make balanced in a minimum number of steps. In each step, you can perform or on the given sequence .
Remove the first element of sequence and insert it as the last element of .
Remove the last element of sequence and insert it as the first element of .
Here, the first element is the leftmost element. The sequence is read left to right. You can perform the operations any number of times. Your task is to minimize the number of operations.
Note that, A balanced parenthesis sequence meets the following two conditions:
It contains no unmatched parenthesis. It means that for each there will be a matched .
The subset of parenthesis enclosed by any matched parenthesis is also balanced.
The first line of the input contains an integer which denotes the number of test cases. Each of the next lines will contain a string which is the parenthesis sequence.
For 10 points:
For 90 points:
For each case of input, print “Case x: y” without quotation marks. If it is not possible to make the sequence valid, print “Case x: impossible”. Here is the case number and is the minimum number of operations you need to make the sequence valid.
3 )((()) )((())) ((()))
Case 1: 1 Case 2: impossible Case 3: 0