Easy Parenthesis

Hasinur_ PIHACKS'21-CodeJam
Limits 1s, 512 MB

Let there be a parenthesis sequence string SS. This sequence is not guaranteed to be balanced. Your task is to make SS balanced in a minimum number of steps. In each step, you can perform F(S)F(S) or G(S)G(S) on the given sequence SS.

F(S)F(S)== Remove the first element of sequence SS and insert it as the last element of SS.

G(S)G(S) ==Remove the last element of sequence SS and insert it as the first element of SS.

Here, the first element is the leftmost element. The sequence SS 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:

  1. It contains no unmatched parenthesis. It means that for each (‘(‘ there will be a matched )‘)’.

  2. The subset of parenthesis enclosed by any matched parenthesis is also balanced.

Input

The first line of the input contains an integer TT which denotes the number of test cases. Each of the next TT lines will contain a string SS which is the parenthesis sequence.

Constraints:\textbf{Constraints:}

For 10 points:

  • 1T20001 \leq T \leq 2000

  • 1S101 \leq |S| \leq 10

For 90 points:

  • 1T1051 \leq T \leq 10^5

  • 1S1051 \leq |S| \leq 10^5

  • 1i=1TSi2×1051 \leq \sum_{i=1}^{T} |S_i| \leq 2 \times 10^5

Output

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 xx is the case number and yy is the minimum number of operations you need to make the sequence valid.

Sample

InputOutput
3
)((())
)((()))
((()))
Case 1: 1
Case 2: impossible
Case 3: 0

Submit

Login to submit.

Statistics

50% Solution Ratio
gokul.rajEarliest, Aug '21
ASH1901041MFastest, 0.0s
Mestu_PaulLightest, 393 kB
Hasan.987326Shortest, 835B
Toph uses cookies. By continuing you agree to our Cookie Policy.