BRCKTS2  Brackets II
Peter is preparing slides for his lecture on parsing arithmetic expressions. In the first part of the lecture he wants to focus just on parsing brackets. He invented an interesting geometric representation of a correct bracket sequence for his students, because one image is better than a thousand words:
Formally, the definition of the geometric representation looks as follows. The simplest correct bracket sequence () is represented by a 1 * 1 square. If A is a correct bracket sequence and g(A) its represenation, then the representation for (A) is g(A) surrounded by a rectangle two units wider than g(A) and one unit taller than the highest point of g(A). If A and B are two correct bracket sequences and g(A) and g(B) are their representations, then we get g(AB) by placing g(B) one unit to the right of g(A).
After he finished his slides, Peter started to play with the images he prepared. He painted the bounded areas of the images alternately black and white, in such a way that the outermost areas are all painted black. For the example above this coloring looks as follows:
Problem specification
You are given a correct bracket sequence. Calculate the area that is colored black.
Input specification
The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of one line with a correct bracket sequence with length less than 350000. Every line will only contain characters ( and ).
Output specification
For each test case output one line with one integer – the area of the black part of the corresponding geometric representation.
Example
Input: 2 ((())) (())(()(())) Output: 10 20
hide comments
Archit Jain:
20160322 09:55:39
use long long 

guru2691:
20141101 17:45:47
use 64 bit integer for all variables!!! 

Ajey Golsangi:
20130615 07:35:33
Got a SIGSEGV flag with recursion, got AC after converting to a non recursive program. 

Tigran:
20130331 08:12:43
I think, recursion works fine for this problem. And I got AC with 2 recursion function which depths in worst case are 350000 / 2. 

Nic Roets:
20121218 21:03:07
@Brian You are right about the grader. However, when testing on my own Linux box, I had to increase it, e.g. 'ulimit s 20000' 

abhishek kumar:
20120415 12:01:40
Any recursion can be changed into iteration by suitable using a stack 

darryl:
20110712 00:59:01
yes, this problem can be done without recursion. 

no:
20101106 08:01:55
can this ques be done without using recursion ?


no:
20101105 05:34:05
are we to print ans subsequently for each test case?


Brian Bi:
20100904 15:25:42
I disagree; in C/C++, recursion depth is limited only by available stack space. On Windows, I think this is only 8 MB, so it's easy to overflow. On the SPOJ grader, stack space is bounded only by total virtual memory, 256 MB. 
Added by:  Fudan University Problem Setters 
Date:  20090531 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  IPSC 2009 