There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
A string s consisting of '(' or ')' (1≤|s|≤106).
For each test case, output an integer m=where ansi is the number of valid substrings which contain i-th character.
2 ()() ((()))
20 42
For the second case, ans={1,2,3,3,2,1}, then m=1⋅1+2⋅2+3⋅3+4⋅3+5⋅2+6⋅1=42