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

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