Dãy ngoặc

Xem dạng PDF

Gửi bài giải


Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho 1 xâu ~s~ có độ dài n gồm các kí tự ), (?. Gọi ~x~ là số cách thay thế các dấu ? trong xâu để tạo thành 1 dãy ngoặc đúng. In ra ~\min(x, 10)~.

Dãy ngoặc đúng được định nghĩa như sau:

  • Xâu rỗng là dãy ngoặc đúng

  • Nếu ~s~ là một dãy ngoặc đúng, ~\texttt{(} + s + \texttt{)}~ cũng là một dãy ngoặc đúng

  • Nếu ~s_1~ và ~s_2~ là hai dãy ngoặc đúng, ~s_1 + s_2~ cũng là một dãy ngoặc đúng

Input

Dòng đầu tiên chứa 1 số nguyên dương ~t~ (~t \le 10^5~) là số lượng bộ test.

Mỗi bộ test bao gồm duy nhất 1 dòng là xâu ~s~.

Tổng độ dài xâu ~s~ trong các bộ test không vượt quá ~10^5~.

Output

Với mỗi bộ test, in ra ~\min(x, 10)~.

Sample Input 1

10
)(??
)(((
())?
))?)
?(?)
?)?(
???)
((?)
)?()
))?(

Sample Output 1

0
0
0
0
1
0
2
1
0
0

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.