Biểu thức ngoặc là xâu chỉ gồm các ký tự '(' hoặc ')'. Biểu thức ngoặc đúng và bậc của biểu thức ngoặc được định nghĩa một cách đệ qui như sau:

• Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng 0,
• Nếu A là biểu thức ngoặc đúng có bậc bằng 𝑘 thì (A) cũng là một biểu thức ngoặc đúng có bậc bằng 𝑘 + 1,
• Nếu A và B là hai biểu thức ngoặc đúng và có bậc tương ứng là 𝑘1 và 𝑘2 thì AB cũng là một biểu thức ngoặc đúng có bậc bằng max(k1,k2).

Ví dụ: '()(())' là một biểu thức ngoặc đúng có bậc bằng 2 còn '(()(()))' là một biểu thức ngoặc đúng và có bậc bằng 3.

Yêu cầu: Cho S là một xâu chỉ gồm các ký tự '(', ')' , hãy kiểm tra xem S là dãy ngoặc bậc bao nhiêu.

Input:

• Dòng 1: xâu S có độ dài không vượt quá ~10^6~ chỉ gồm các ký tự '(', ')'

Output:

• Ghi số nguyên dương t là số bậc cao nhất của dãy ngoặc S.

Ví dụ:

Input 1:

()()

Output 1:

1

Input 2:

((()))

Output 2:

3

Ràng buộc

Subtask 1: ~s.length() \le 20~

Subtask 2: Không có bất cứ ràng buộc nào.