안정적인 문자열

여는 괄호 { 와 닫는 괄호 } 로만 이루어진 문자열이 주어진다. 이 문자열을 안정적인 문자열로 만들기 위해 필요한 최소 연산 횟수를 구하여라.

안정적인 문자열은 다음과 같이 정의된다.

1. 빈 문자열은 안정적이다.
2. 문자열 $S$ 가 안정적이면, $\{S\}$ 도 안정적이다.
3. 문자열 $S$ 와 $T$ 가 안정적이면, 두 문자열을 이어 붙인 $ST$ 도 안정적이다.

예를 들어 {}, {}{}, {{}{}} 는 안정적이지만, }{, {{}{, {}{ 는 안정적이지 않다.

문자열에 적용할 수 있는 연산은 다음 두 가지이다.

• 여는 괄호 { 를 닫는 괄호 } 로 바꾼다.
• 닫는 괄호 } 를 여는 괄호 { 로 바꾼다.

입력은 여러 개의 데이터 세트로 이루어진다. 각 데이터 세트는 한 줄이며, 여는 괄호 { 와 닫는 괄호 } 로만 이루어진 문자열이 주어진다. 각 문자열의 길이는 $2000$ 을 넘지 않으며, 항상 짝수이다.

입력의 마지막 줄에는 하이픈 - 이 한 개 이상 주어지며, 이 줄은 처리하지 않는다.

각 데이터 세트마다 한 줄씩 출력한다. 각 줄에는 데이터 세트의 번호($1$ 부터 시작하며 등장한 순서대로 매긴다)와 그 문자열을 안정적으로 만드는 데 필요한 최소 연산 횟수를 번호. 횟수 형식으로 출력한다.