Practice Coding with the exercise "Brackets, Ultimate Edition"

Statement

Goal

You must determine the minimum number of bracket-flipping operations needed to make a given expression valid. An expression has a valid bracketing when all the parentheses (), square brackets [], curly braces {} and angle brackets <> are correctly paired and nested.

You can flip a bracketing element in-place by replacing it with its counterpart, e.g. replace a ( with a ), or a > with a <. For example, flipping both parentheses around in the expression below would make it valid with a cost of 2:

<{[)abc(]}> → <{[(abc)]}>

(This is an arguably harder variant of community puzzle “Brackets, Enhanced Edition”. You may want to complete that one first.)

Input

Line 1: the number N of expressions
Next N lines: an expression

Output

N lines: the number F of flips needed to make the expression valid. If the expression cannot be made valid, output -1.

Constraints

N ≤ 100
expression length ≤ 10000
number of bracketing elements ≤ 25
The expression contains no whitespace.

Example

Input

2
<{[(abc(]}>
<{[(abc>}])

Output

1
-1

Solve it

A higher resolution is required to access the IDE