Easy Parenthesis

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

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

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

Here, the first element is the leftmost element. The sequence $S$ 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 $T$ which denotes the number of test cases. Each of the next $T$ lines will contain a string $S$ which is the parenthesis sequence.

$\textbf{Constraints:}$

For 10 points:

• $1 \leq T \leq 2000$

• $1 \leq |S| \leq 10$

For 90 points:

• $1 \leq T \leq 10^5$

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

• $1 \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 $x$ is the case number and $y$ is the minimum number of operations you need to make the sequence valid.

Sample

3
)((())
)((()))
((()))

Case 1: 1
Case 2: impossible
Case 3: 0