Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

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

Được gửi lên bởi:Hacker7
Ngày:2012-12-19
Thời gian chạy:15s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:2012 ACM Asia Hanoi Regional; Problem setter: Lê Minh Hoàng; TestData rebuild by Lê Yên Thanh

hide comments
2018-01-04 04:04:00
nhật hào sạch
2016-02-01 09:23:14
THAM KHAO http://codevnspoj.blogspot.com/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.