A. CBS Bracket Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After Da7doo7 got fired from his previous job, he Started a business of fixing bracket sequences and he needs your help.

You are given a bracket sequence$$$^\dagger$$$ and you want to apply some operations (possibly zero) to make it a regular bracket sequence$$$^\ddagger$$$.

In each operation, two brackets will be appended to the sequence, one of them at the beginning and the other at the end of the sequence, you can choose the state of each bracket as you wish.

In other words, let the current sequence be $$$s$$$. After applying one operation $$$s$$$ will become one of these sequences:

  • $$$s \; \gets \; \texttt{(} s \texttt{(}$$$
  • $$$s \; \gets \; \texttt{(} s \texttt{)}$$$
  • $$$s \; \gets \; \texttt{)} s \texttt{(}$$$
  • $$$s \; \gets \; \texttt{)} s \texttt{)}$$$

You are asked to find the minimum number of operations required to make $$$s$$$ a regular bracket sequence$$$^\ddagger$$$ or report that it is impossible.

$$$^\dagger$$$ A bracket sequence is a string containing only the characters "(" and ")".

$$$^\ddagger$$$ A regular bracket sequence is a bracket sequence that can be transformed into a valid math expression by inserting characters "1" and "+" between the original characters of the sequence. For example:

  • the bracket sequences "()()" and "(())" are regular becuase their resulting expressions are "(1)+(1)" and "((1+1)+1)" respectively.
  • the bracket sequences ")(", "(" and ")" are not.
Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 10^5)$$$ denoting the number of test cases.

Each of the following $$$T$$$ lines contains a bracket sequence $$$s$$$ $$$(1\le |s|\le 5\cdot 10^5)$$$.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, if there is no way to make $$$s$$$ regular, print $$$-1$$$. Otherwise, print the minimum number of operations required to make $$$s$$$ regular.

Example
Input
3
)(()
)((
(())
Output
1
-1
0