Một dãy ngoặc đúng là một xâu gồm các ký tự (, ), [, ], { và } định nghĩa như sau:

• Xâu rỗng (không có ký tự nào) là một dãy ngoặc đúng
• Nếu \(A\) và \(B\) là hai dãy ngoặc đúng thì \(AB\) (xâu tạo thành bằng cách lấy xâu \(A\) nối vào trước xâu \(B\)) cũng là một dãy ngoặc đúng
• Nếu \(A\) là một dãy ngoặc đúng thì (A), [A] và {A} cũng là những dãy ngoặc đúng
• Những xâu không thành lập được theo quy tắc trên không phải là dãy ngoặc đúng

Ví dụ {[()()[]()]}() là một dãy ngoặc đúng nhưng [(]) và }}}{{{ không phải là những dãy ngoặc đúng.

Yêu cầu: Cho xâu ký tự \(S\) có độ dài không quá \(300\) và chỉ gồm các ký tự: ()[]{}, hãy xóa đi một số ít nhất các ký tự trong \(S\) để được một dãy ngoặc đúng, cho biết số ký tự phải xóa.

Input

• một dòng chứa xâu \(S\)

Output

• Ghi ra số ký tự phải xóa

Example

}}}][[[

7

{[()()[]}[]()]}()

1

{[(}[]]) 

4