You are provided a balanced bracket sequence $S$. A super balanced bracket is a balanced bracket sequence that has the following structure:

$((((......))))$

Here, all the opening brackets must contain corresponding closing brackets and all opening brackets must appear before any closing brackets. For example, $(())$ and $((()))$ are super balanced sequence but $()()$ and $(()())$ are not the super balanced sequence because there exists an opening bracket that appears after a closing bracket.

Your task is to determine the size of the largest super balanced bracket subsequence that is formed over all subsequences of the original sequence.

Input format

• First line: $T$ denoting the number of test cases
• Next $T$ lines: Each line contains $S$ that denotes the balanced bracket sequence

Output format

For each test case, print the answer in a single line

Constraints

$1\leq T\leq7\\ 2\leq|S|\leq 10^5, |S|\ is\ even$

• $S$ is balanced and contains only $($ and $)$