문제

올바른 괄호 문자열은 다음 규칙을 만족하는 문자열이다.

• 빈 문자열은 올바른 괄호 문자열이다.
• A가 올바른 괄호 문자열이라면, (A)도 올바른 괄호 문자열이다.
• A와 B가 각각 올바른 괄호 문자열이라면, AB도 올바른 괄호 문자열이다.

(와 )로만 이루어진 문자열 S가 주어질 때, 이 문자열의 공백이 아닌 모든 부분 문자열 중 올바른 괄호 문자열인 것의 개수를 세보자.

입력

첫째 줄에 테스트케이스의 개수 $T$이 주어진다. ($1\le T\le 100$)

둘째 줄부터 $T$개의 줄에 걸쳐 각 줄에 문자열 $S$가 주어진다. ($1\le |S|\le 200\,000$)

모든 테스트케이스에서 $|S|$의 합은 $200\,000$을 초과하지 않는다.

출력

$T$개의 줄에 걸쳐 각 줄에 $S$의 공백이 아닌 모든 부분 문자열 중 올바른 괄호 문자열인 것의 개수를 출력한다

예제 입력 1

5
()
()()()
(())())
)(
()))(()))()()((())(()()()))))()()()())))((

예제 출력 1

1
6
4
0
29