Migrated from Lutece 10 In Galgame We Trust

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

As we all know, there are many interesting (H) games in kennethsnow’s computer. But he sets a password for those games. Zplinti1 wants to crack his password and play those games.

Kennethsnow uses only $6$ kinds of characters to form his password:

1. brackets: ( and )
2. square brackets: [ and ]
3. curly brackets: { and }

Kennethsnow’s password must be a correct bracket sequence, and will not be empty.

Zplinti1 found a string written by kennethsnow, and he is sure that kennethsnow’s password is a substring of that, he wonders the maximum possible length of his password, or if his judgment is wrong.

Please note that the original string may also be the password.

Input

The first line of input contains a number $T$, indicating the number of test cases. ($T\leq 30$) For each case, there is a string s, which is the string zplinti1 found. ($1\leq |s|\leq 1,000,000$, the string will contain those $6$ kinds of characters only)

Output

For each case, output Case #i: first. ($i$ is the number of the test case, from $1$ to $T$). If zplinti1’s judgment is wrong (i.e. the answer is $0$), output I think H is wrong!, otherwise output a single number, indicating the maximum possible length of kennethsnow’s password.

Samples

3
(){[]}
{([(])}
))[{}]]

Case #1: 6
Case #2: I think H is wrong!
Case #3: 4

Note

We can define a correct bracket sequence more precisely in this way:

Strings (), [], and {} are correct.

For each correct sequence A, (A), [A], {A} is also correct.

For each correct sequence A and B, AB is also correct.

Resources

The 11th UESTC Programming Contest Final