Is This a Give-Away?

Once there lived an ancient mage named Farabi. He could always give perfect weather forecast. He never revealed how. After he died no one could predict the weather perfectly anymore. In his lifetime, he wrote a book in an encrypted language. After so many years and so many trials, a brilliant coder named Masum broke the encryption.

After decryption, Masum found out the key to the weather forecast. Considering the waves of the rivers around, he can get a sequence consisting of curly braces ('{', '}'). The maximum depth that can be achieved after removing some or no curly braces, that means the depth of maximum nested curly bracket sequence that can be created, is the key to everything. Masum wants you to build a system for it while he finds out the sequence.

For example, in the bracket sequence "{{}}{}" The maximum depth is 2.

Input

Input contains a string $s$ ($|s| \le 10^5$) containing '{' and '}' only.

Output

Print one integer denoting the answer.

Sample

Input	Output
{{}{}{}}	3
In the given sample, if we remove the 3rd and 6th braces, we will get {{{}}} which will have a depth 3. There is no other way to get more than 3.