# Brackets, Ultimate Edition

Difficulty : Medium

Community success rate: 64%

Approved by eulerscheZahl Plopx an anonymous CodinGamer

A higher resolution is required to access the IDE

- 65

## 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 parenthesesYou can flip a bracketing element in-place by replacing it with its counterpart, e.g. replace a

<{[)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**an expression

`N`lines:Output

**the number**

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

Constraints

`N`≤ 100

expression length ≤ 10000

number of bracketing elements ≤ 25

The expression contains no whitespace.

Example

Input

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

Output

1 -1

A higher resolution is required to access the IDE