Brackets#1653

Brackets

1 second
122.174 megabytes
Easy

Let be a proper bracketing sequence if it consists only of the characters , , , , , and satisfies at least one of the following three conditions:

  1. is an empty string;

  2. can be represented as \textbf{S} = S_1 + S_2 + S_3 + \ldots + S_n (n > 1), where S_i are non-empty proper bracketing sequences, and the "" sign denotes string concatenation;

  3. can be represented as \textbf{S} = \textbf{\{} + C + \textbf{\}}, \textbf{S} = \textbf{[} + C + \textbf{]}, or \textbf{S} = \textbf{(} + C + \textbf{)}, where is a proper bracketing sequence.

A string is given, consisting only of the characters , , , , , . Determine the minimum number of characters that need to be inserted to make it a proper bracketing sequence.

Input

A single string consisting of at most characters from , , , , , .

Output

Print a single non-negative integer — the answer to the problem.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading