DBRACKET - Dãy ngoặc đúng phân biệt

Giới hạn
  • Thời gian: 15.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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: "()" ; "()()"; "(()())"; "(()())()"

  • Người up: yenthanh132
  • Nguồn bài: 2012 ACM Asia Hanoi Regional; Problem setter: Lê Minh Hoàng; TestData rebuild by Lê Yên Thanh