Giải bài trực tuyến

Người ta định nghĩa một dãy ngoặc đúng như sau:

• Xâu rỗng là một dãy ngoặc đúng.
• Nếu A là dãy ngoặc đúng thì (A) cũng là một dãy ngoặc đúng
• Nếu A, B là những dãy ngoặc đúng thì AB cũng là dãy ngoặc đúng.

Những dãy ngoặc sau được xem là đúng:

• ()(())
• ((()))

Những dãy ngoặc sau thì không:

• )(
• (((()))
• )()()(

Một xâu S khác rỗng được gọi là xâu con của T nếu xâu S trùng với một dãy các kí tự liên tiếp của T. Ví dụ "bcd" là xâu con của xâu "abcde" nhưng xâu "dc" thì không.

Cho một xâu T chỉ gồm các kí tự '(' và ')'  (kí tự mở ngoặc và đóng ngoặc). Như vậy các xâu con của T có thể là một dãy ngoặc đúng hoặc không. Hãy đếm số lượng xâu con phân biệt của T mà là một dãy ngoặc đúng.

Input

• Dòng đầu tiên chứa số n là số lượng bộ test (n<=20).
• n dòng tiếp theo, mỗi dòng là một bộ test chứa xâu T. Biết rằng độ dài của xâu T không vượt quá 100.000 kí tự.

Output

• Với mỗi bộ test, xuất ra số lượng xâu con phân biệt của T mà là một dãy ngoặc đúng.

Example

Input:
3
(()())()
(()()()()()
()()()(()())(()())

Output:
4
5
11

Giải thích: Với bộ test đầu, có 4 xâu con phân biệt là một dãy ngoặc đúng: "()" ; "()()"; "(()())"; "(()())()"