Исправить расстановку скобок

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

Всего имеется три вида скобок: обычные (), квадратные [] и фигурные {}. Каждая пара скобок содержит соответственно открывающийся ('(', '[', '{' ) и закрывающийся (')', ']', '}') символ.

Правильная строка определяется следующими правилами:

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

Например, строки "([{}])", "" и "(){}[]" являются правильными, а "([}]", "([)]" и "{" нет.

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

Входные данные

Каждая строка содержит четное количество символов '(', ')', '[', ']', '{', '}'. Длина каждой строки не более 50.

Выходные данные

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