Виправити розстановку дужок
У заданому рядку з дужок слід змінити найменшу кількість символів так, щоб отриманий рядок був правильним. Видаляти чи вставляти символи неможна.
Усього є три види дужок: звичайні (), квадратні [] та фігурні {}. Кожна пара дужок містить відповідно символ відкритої дужки ('(', '[', '{' ) та закритої дужки (')', ']', '}').
Правильний рядок визначається наступними правилами:
Порожній рядок є правильним.
Якщо рядок s є правильним, то правильними будуть також (s), [s] та {s}.
Якщо рядки s та t правильні, то правильним буде рядок st.
Наприклад, рядки "([{}])", "" та "(){}[]" є правильними, а "([}]", "([)]" та "{" ні. Для заданого рядку слід змінити найменшу кількість символів так, щоб він став правильним.
Вхідні дані
Кожний рядок містить парну кількість символів '(', ')', '[', ']', '{', '}'. Довжина кожного рядка не більша за 50.
Вихідні дані
Для кожного дужкового запису вивести в окремому рядку найменшу кількість символів, яку можна змінити так, щоб рядок став правильним.