Description

Let us define a regular brackets sequence in the following way:

1. Empty sequence is a regular sequence.

2. If S is a regular sequence, then (S) is a regular sequence.

3. If A and B are regular sequences, then AB is a regular sequence.

For example, these sequences of characters are regular brackets sequences: (), (()), ()(), ()(()), ((())())().

And all the following character sequences are not: (, ), ((), ()), ())(, (()(, ()))().

A sequence of characters '(' and ')' is given. You can insert only one '(' or ')' into the left of the sequence, the right of the sequence, or the place between any two adjacent characters, to try changing this sequence to a regular brackets sequence.

Input

The first line has a integer T (1 <= T <= 200), means there are T test cases in total.

For each test case, there is a sequence of characters '(' and ')' in one line. The length of the sequence is in range [1, 105].

Output

For each test case, print how many places there are, into which you insert a '(' or ')', can change the sequence to a regular brackets sequence.

What's more, you can assume there has at least one such place.

Sample Input

4
)
())
(()(())
((())())(()

Sample Output

1
3
7
3

Hint

题意：给定一个括号字符串，插入一个括号使得所有的括号匹配，问有多少处可以插入括号

思路：定义（ 的值为1 ） 的值为-1，用以数组记录每个位置的值，遇（ +1 遇 ）-1，当第一次出现-1时，则前面的所有位置都可以加括号

#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
string s;
int cal[100010];
int main()
{
	int T;
	while (cin >> T)
	{
		while (T--)
		{
			memset(cal, 0, sizeof(cal));
			cin >> s;
			int sum = 0;
			for (int i = 0; i < s.length(); i++)
			{
				int pre;
				if (i == 0)
					pre = 0;
				else
					pre = i - 1;
				if (s[i] == '(')
					cal[i] = cal[pre] + 1;
				else if (s[i] == ')')
					cal[i] = cal[pre] - 1;
			}
			for (int i = 0; i < s.length(); i++)
			{
				if (cal[i] == -1)
				{
					sum = sum + i + 1;
					break;
				}
			}
                        //反着再来一遍    
			for (int i = s.length() - 1; i >= 0; i--)
			{
				if (s[i] == '(')
					cal[i] = cal[i+1] + 1;
				else if (s[i] == ')')
					cal[i] = cal[i+1] - 1;
			}
			for (int i = s.length() - 1; i >= 0; i--)
			{
				if (cal[i] == 1)
				{
					sum = sum + s.length() - i;
					break;
				}
			}
			cout << sum << endl;
		}
	}
	return 0;
}
/**********************************************************************
	Problem: 1271
	User: leo6033
	Language: C++
	Result: AC
	Time:152 ms
	Memory:2728 kb
**********************************************************************/