У заданому рядку з дужок слід змінити найменшу кількість символів так, щоб отриманий рядок був правильним. Видаляти чи вставляти символи неможна.

Усього є три види дужок: звичайні (), квадратні [] та фігурні {}. Кожна пара дужок містить відповідно символ відкритої дужки ('(', '[', '{' ) та закритої дужки (')', ']', '}').

Правильний рядок визначається наступними правилами:

• Порожній рядок є правильним.
• Якщо рядок s є правильним, то правильними будуть також (s), [s] та {s}.
• Якщо рядки s та t правильні, то правильним буде рядок st.

Наприклад, рядки "([{}])", "" та "(){}[]" є правильними, а "([}]", "([)]" та "{" ні. Для заданого рядку слід змінити найменшу кількість символів так, щоб він став правильним.

Вхідні дані

Кожний рядок містить парну кількість символів '(', ')', '[', ']', '{', '}'. Довжина кожного рядка не більша за 50.

Вихідні дані

Для кожного дужкового запису вивести в окремому рядку найменшу кількість символів, яку можна змінити так, щоб рядок став правильним.

Вхідні дані #1

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

Відповідь #1

3
2
1