Don't you hate it when there's something wrong with brackets in your code? Don't know if our proposed solution is good in terms of user experience, but we won't know untill we try!

I'll give you a string that consists only of 2 type of brackets: square ('[', ']') and round ('(', ')'). We want this string to be turned into a balanced string by zero or more operations. We have only one kind of operations: replace a bracket by another bracket, and it has a cost of 1.

A balanced string is either:

an empty string.

the concatenation of 2 balanced strings.

the concatenation of the string "[", a balanced string, and the string "]".

the concatenation of the string "(", a balanced string, and the string ")".

Yes, the definition above is recursive. If you prefer formal notation, that's its BNF:

balancedString = emptyString | balancedString balancedString | [balancedString] | (balancedSstring)

The '|' means OR.

For example, "()[()](())([[]()()[[]]()])", "()", "()[]", "(())", "[][]" are all balanced strings. While ")", "(", "[(])", "[([]])" are not.

What is the minimum cost needed to balance the given string?

Input

The input file consists of t (1 ≤ t ≤ 128) test cases.

Each test case consists of a single line - the given string s (1 ≤ s ≤ 50).

si  in {'(' , ')', '[' , ']'}.

Output

The minimum cost needed to balance the given string or -1 if it's impossible.

STDIN

This is the content of the STDIN.

3
[(])
(
([])

STDOUT

Your solution should produce a similar result.

2
-1
0