Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Easy Parenthesis

By Hasinur_ · 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

    Discussion

    Statistics


    50% Solution Ratio

    gokul.rajEarliest, 1M ago

    ASH1901041MFastest, 0.0s

    Mestu_PaulLightest, 393 kB

    Hasan.987326Shortest, 835B

    Submit

    Login to submit

    Related Contests

    Toph uses cookies. By continuing you agree to our Cookie Policy.