시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 448 184 169 43.445%

문제

여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.

  1. 빈 문자열은 안정적이다.
  2. S가 안정적이라면, {S}도 안정적인 문자열이다.
  3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

입력

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.

입력의 마지막 줄은 '-'가 한 개 이상 주어진다.

출력

각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.

예제 입력 1

}{
{}{}{}
{{{}
---

예제 출력 1

1. 2
2. 0
3. 1
W3sicHJvYmxlbV9pZCI6IjQ4ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1ZWNcdWIyOTQgXHVhZDA0XHVkNjM4XHVjNjQwIFx1YjJlYlx1YjI5NCBcdWFkMDRcdWQ2MzhcdWI5Y2NcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyBcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWM4MTVcdWM3NThcdWI3ODAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJlNDggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzU0OFx1YzgxNVx1YzgwMVx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+U1x1YWMwMCBcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzRcdWI3N2NcdWJhNzQsIHtTfVx1YjNjNCBcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5TXHVjNjQwIFRcdWFjMDAgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc0XHViNzdjXHViYTc0LCBTVChcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzVmMFx1YWNiMClcdWIzYzQgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPnt9LCB7fXt9LCB7e317fX1cdWIyOTQgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YzljMFx1YjljYywgfXssIHt7fXssIHt9e1x1YjI5NCBcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwIFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc0MCBcdWM1ZWNcdWIyOTQgXHVhZDA0XHVkNjM4XHViOTdjIFx1YjJlYlx1YjI5NCBcdWFkMDRcdWQ2MzhcdWI4NWMgXHViYzE0XHVhZmI4XHVhYzcwXHViMDk4LCBcdWIyZWJcdWIyOTQgXHVhZDA0XHVkNjM4XHViOTdjIFx1YzVlY1x1YjI5NCBcdWFkMDRcdWQ2MzhcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1YWM4MyAyXHVhYzAwXHVjOWMwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1ZWNcdWIyOTQgXHVhZDA0XHVkNjM4XHVjNjQwIFx1YjJlYlx1YjI5NCBcdWFkMDRcdWQ2MzhcdWI5Y2NcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgMjAwMFx1Yzc0NCBcdWIxMThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YWNlMCwgXHVkNTZkXHVjMGMxIFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWM5ZGRcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNzQwICYjMzk7LSYjMzk7XHVhYzAwIFx1ZDU1YyBcdWFjMWMgXHVjNzc0XHVjMGMxIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHVjNjQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0Jm5ic3A7XHVjNTQ4XHVjODE1XHVjODAxXHVjNzNjXHViODVjIFx1YmMxNFx1YWZiOFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ4ODkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTZWluZmVsZCIsImRlc2NyaXB0aW9uIjoiPHA+SSZyc3F1bzttIG91dCBvZiBzdG9yaWVzLiBGb3IgeWVhcnMgSSZyc3F1bzt2ZSBiZWVuIHdyaXRpbmcgc3Rvcmllcywgc29tZSByYXRoZXIgc2lsbHksIGp1c3QgdG8gbWFrZSBzaW1wbGUgcHJvYmxlbXMgbG9vayBkaVx1ZmIwM2N1bHQgYW5kIGNvbXBsZXggcHJvYmxlbXMgbG9vayBlYXN5LiBCdXQsIGFsYXMsIG5vdCBmb3IgdGhpcyBvbmUuPFwvcD5cclxuXHJcbjxwPllvdSZyc3F1bztyZSBnaXZlbiBhIG5vbiBlbXB0eSBzdHJpbmcgbWFkZSBpbiBpdHMgZW50aXJldHkgZnJvbSBvcGVuaW5nIGFuZCBjbG9zaW5nIGJyYWNlcy4gWW91ciB0YXNrIGlzIHRvIFx1ZmIwMW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiAmbGRxdW87b3BlcmF0aW9ucyZyZHF1bzsgbmVlZGVkIHRvIG1ha2UgdGhlIHN0cmluZyBzdGFibGUuIFRoZSBkZVx1ZmIwMW5pdGlvbiBmb3IgYmVpbmcgc3RhYmxlIGlzIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+QW4gZW1wdHkgc3RyaW5nIGlzIHN0YWJsZS48XC9saT5cclxuXHQ8bGk+SWYgUyBpcyBzdGFibGUsIHRoZW4ge1N9IGlzIGFsc28gc3RhYmxlLjxcL2xpPlxyXG5cdDxsaT5JZiBTIGFuZCBUIGFyZSBib3RoIHN0YWJsZSwgdGhlbiBTVCAodGhlIGNvbmNhdGVuYXRpb24gb2YgdGhlIHR3bykgaXMgYWxzbyBzdGFibGUuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+QWxsIG9mIHRoZXNlIHN0cmluZ3MgYXJlIHN0YWJsZToge30sIHt9e30sIGFuZCB7e317fX07IEJ1dCBub25lIG9mIHRoZXNlOiB9eywge3t9eywgbm9yIHt9ey4gVGhlIG9ubHkgb3BlcmF0aW9uIGFsbG93ZWQgb24gdGhlIHN0cmluZyBpcyB0byByZXBsYWNlIGFuIG9wZW5pbmcgYnJhY2Ugd2l0aCBhIGNsb3NpbmcgYnJhY2UsIG9yIHZpc2EtdmVyc2EuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSB0ZXN0ZWQgb24gb25lIG9yIG1vcmUgZGF0YSBzZXRzLiBFYWNoIGRhdGEgc2V0IGlzIGRlc2NyaWJlZCBvbiBhIHNpbmdsZSBsaW5lLiBUaGUgbGluZSBpcyBhIG5vbi1lbXB0eSBzdHJpbmcgb2Ygb3BlbmluZyBhbmQgY2xvc2luZyBicmFjZXMgYW5kIG5vdGhpbmcgZWxzZS4gTm8gc3RyaW5nIGhhcyBtb3JlIHRoYW4gMjAwMCBicmFjZXMuIEFsbCBzZXF1ZW5jZXMgYXJlIG9mIGV2ZW4gbGVuZ3RoLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBsaW5lIG9mIHRoZSBpbnB1dCBpcyBtYWRlIG9mIG9uZSBvciBtb3JlICZyc3F1bzstJnJzcXVvOyAobWludXMgc2lnbnMuKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIGZvbGxvd2luZyBsaW5lOjxcL3A+XHJcblxyXG48cHJlPmsuIE48XC9wcmU+XHJcblxyXG48cD5XaGVyZSBrIGlzIHRoZSB0ZXN0IGNhc2UgbnVtYmVyIChzdGFydGluZyBhdCBvbmUsKSBhbmQgTiBpcyB0aGUgbWluaW11bSBudW1iZXIgb2Ygb3BlcmF0aW9ucyBuZWVkZWQgdG8gY29udmVydCB0aGUgZ2l2ZW4gc3RyaW5nIGludG8gYSBiYWxhbmNlZCBvbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d