시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB94129923738.537%

문제

깊은 아마존 정글에 거대한 나무들에서 갈색 원숭이들이 매우 좋아하는 무화과가 열리고, 이 나무에는 향나무노린재들이 서식하고 있다.

나무 꼭대기에 도달하기 위해서 원숭이들은 매우 조심스럽게 나무에 올라가는 길을 찾아야한다. 거대한 나무는 부서지기 쉬운 덩굴들이 있는데 이 덩굴들은 시소의 원리와 비슷하다. 덩굴의 무게가 불균형 하면 그 덩굴은 끊어지며 그 원숭이들은 땅으로 떨어져버린다. 원숭이들은 서로 협력하여 덩굴의 균형을 유지한다면 그들은 모두 무화과가 열리고 향나무노린재들이 서식하는 나무 꼭대기에 도달할 수 있다는 것을 발견했다.

덩굴은 두개의 덩굴로 나눠질 수 있는데 덩굴이 끊어지지 않기 위해서는 나눠진 두 덩굴은 같은 수의 원숭이들이 매달려 있어야한다. 덩굴의 나눠지는 지점을 "[]"로 정의 내리면 덩굴의 구조를 꺾쇠괄호로 표시할 수 있다. 또한 덩굴의 깊이는 25를 넘지 않는다.

원숭이들은 덩굴의 균형을 유지하면서 나무꼭대기에 도달할 수 있는 최소 원숭이 수를 알고 싶다. 나무 꼭대기에 도달하기 위해서 최소 한 마리 원숭이가 필요하다.

입력

첫째 줄에 테스트 케이스의 개수 N(1 ≤ N ≤ 1000)이 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, 덩굴의 구조를 꺾쇠괄호로 표현한 문자열이 주어진다. 문자열의 길이는 0보다 크거나 같고, 150보다 작거나 같다.

출력

각 테스트 케이스마다 덩굴의 균형을 유지하면서 나무꼭대기에 도달할 수 있는 최소 원숭이 수를 출력한다.

예제 입력 1

3
[]

[[][[]]]

예제 출력 1

2
1
8

힌트

예제 입력의 2번째 테스트 케이스는 빈 줄 입니다.

W3sicHJvYmxlbV9pZCI6IjI3MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDBcdWMyMmRcdWM3NzQgXHViOWU0XHViMmVjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlNGFcdWM3NDAgXHVjNTQ0XHViOWM4XHVjODc0IFx1YzgxNVx1YWUwMFx1YzVkMCBcdWFjNzBcdWIzMDBcdWQ1NWMgXHViMDk4XHViYjM0XHViNGU0XHVjNWQwXHVjMTFjIFx1YWMwOFx1YzBjOSBcdWM2ZDBcdWMyMmRcdWM3NzRcdWI0ZTRcdWM3NzQgXHViOWU0XHVjNmIwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWJiMzRcdWQ2NTRcdWFjZmNcdWFjMDAgXHVjNWY0XHViOWFjXHVhY2UwLCBcdWM3NzQgXHViMDk4XHViYjM0XHVjNWQwXHViMjk0IFx1ZDVhNVx1YjA5OFx1YmIzNFx1YjE3OFx1YjliMFx1YzdhY1x1YjRlNFx1Yzc3NCBcdWMxMWNcdWMyZGRcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIwOThcdWJiMzQgXHVhZjJkXHViMzAwXHVhZTMwXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjNmQwXHVjMjJkXHVjNzc0XHViNGU0XHVjNzQwIFx1YjllNFx1YzZiMCBcdWM4NzBcdWMyZWNcdWMyYTRcdWI3ZmRcdWFjOGMgXHViMDk4XHViYjM0XHVjNWQwIFx1YzYyY1x1Yjc3Y1x1YWMwMFx1YjI5NCBcdWFlMzhcdWM3NDQgXHVjYzNlXHVjNTQ0XHVjNTdjXHVkNTVjXHViMmU0LiBcdWFjNzBcdWIzMDBcdWQ1NWMgXHViMDk4XHViYjM0XHViMjk0IFx1YmQ4MFx1YzExY1x1YzljMFx1YWUzMCBcdWMyNmNcdWM2YjQgXHViMzY5XHVhZDc0XHViNGU0XHVjNzc0IFx1Yzc4OFx1YjI5NFx1YjM3MCBcdWM3NzQgXHViMzY5XHVhZDc0XHViNGU0XHVjNzQwIFx1YzJkY1x1YzE4Y1x1Yzc1OCBcdWM2ZDBcdWI5YWNcdWM2NDAgXHViZTQ0XHVjMmI3XHVkNTU4XHViMmU0LiBcdWIzNjlcdWFkNzRcdWM3NTggXHViYjM0XHVhYzhjXHVhYzAwIFx1YmQ4OFx1YWRlMFx1ZDYxNSBcdWQ1NThcdWJhNzQgXHVhZGY4IFx1YjM2OVx1YWQ3NFx1Yzc0MCBcdWIwNGFcdWM1YjRcdWM5YzBcdWJhNzAgXHVhZGY4IFx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWI1NDVcdWM3M2NcdWI4NWMgXHViNWE4XHVjNWI0XHVjODM4XHViYzg0XHViOWIwXHViMmU0LiBcdWM2ZDBcdWMyMmRcdWM3NzRcdWI0ZTRcdWM3NDAgXHVjMTFjXHViODVjIFx1ZDYxMVx1YjgyNVx1ZDU1OFx1YzVlYyBcdWIzNjlcdWFkNzRcdWM3NTggXHVhZGUwXHVkNjE1XHVjNzQ0IFx1YzcyMFx1YzljMFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWFkZjhcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIFx1YmIzNFx1ZDY1NFx1YWNmY1x1YWMwMCBcdWM1ZjRcdWI5YWNcdWFjZTAgXHVkNWE1XHViMDk4XHViYjM0XHViMTc4XHViOWIwXHVjN2FjXHViNGU0XHVjNzc0IFx1YzExY1x1YzJkZFx1ZDU1OFx1YjI5NCBcdWIwOThcdWJiMzQgXHVhZjJkXHViMzAwXHVhZTMwXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjM2OVx1YWQ3NFx1Yzc0MCBcdWI0NTBcdWFjMWNcdWM3NTggXHViMzY5XHVhZDc0XHViODVjIFx1YjA5OFx1YjIyMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwIFx1YjM2OVx1YWQ3NFx1Yzc3NCBcdWIwNGFcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWIwOThcdWIyMjBcdWM5YzQgXHViNDUwIFx1YjM2OVx1YWQ3NFx1Yzc0MCBcdWFjMTlcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc3NCBcdWI5ZTRcdWIyZWNcdWI4MjQgXHVjNzg4XHVjNWI0XHVjNTdjXHVkNTVjXHViMmU0LiBcdWIzNjlcdWFkNzRcdWM3NTggXHViMDk4XHViMjIwXHVjOWMwXHViMjk0IFx1YzljMFx1YzgxMFx1Yzc0NCAmcXVvdDtbXSZxdW90O1x1Yjg1YyBcdWM4MTVcdWM3NTggXHViMGI0XHViOWFjXHViYTc0IFx1YjM2OVx1YWQ3NFx1Yzc1OCBcdWFkNmNcdWM4NzBcdWI5N2MgXHVhZWJlXHVjMWUwXHVhZDA0XHVkNjM4XHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHViMzY5XHVhZDc0XHVjNzU4IFx1YWU0YVx1Yzc3NFx1YjI5NCAyNVx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC91cGxvYWRcL2ltYWdlc1wvbW9ua2V5LnBuZ1wiIHN0eWxlPVwid2lkdGg6IDUyMHB4OyBoZWlnaHQ6IDI5NHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2ZDBcdWMyMmRcdWM3NzRcdWI0ZTRcdWM3NDAgXHViMzY5XHVhZDc0XHVjNzU4IFx1YWRlMFx1ZDYxNVx1Yzc0NCBcdWM3MjBcdWM5YzBcdWQ1NThcdWJhNzRcdWMxMWMgXHViMDk4XHViYjM0XHVhZjJkXHViMzAwXHVhZTMwXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWM2ZDBcdWMyMmRcdWM3NzQgXHVjMjE4XHViOTdjIFx1YzU0Y1x1YWNlMCBcdWMyZjZcdWIyZTQuIFx1YjA5OFx1YmIzNCBcdWFmMmRcdWIzMDBcdWFlMzBcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWNkNWNcdWMxOGMgXHVkNTVjIFx1YjljOFx1YjlhYyBcdWM2ZDBcdWMyMmRcdWM3NzRcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBOKDEgJmxlOyBOICZsZTsgMTAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YjM2OVx1YWQ3NFx1Yzc1OCBcdWFkNmNcdWM4NzBcdWI5N2MgXHVhZWJlXHVjMWUwXHVhZDA0XHVkNjM4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1YyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTUwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViMzY5XHVhZDc0XHVjNzU4IFx1YWRlMFx1ZDYxNVx1Yzc0NCBcdWM3MjBcdWM5YzBcdWQ1NThcdWJhNzRcdWMxMWMgXHViMDk4XHViYjM0XHVhZjJkXHViMzAwXHVhZTMwXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWM2ZDBcdWMyMmRcdWM3NzQgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNjA4XHVjODFjIFx1Yzc4NVx1YjgyNVx1Yzc1OCAyXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViZTQ4IFx1YzkwNCBcdWM3ODVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNzE2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTW9ua2V5IFZpbmVzIiwiZGVzY3JpcHRpb24iOiI8cD5EZWVwIGluIHRoZSBBbWF6b24ganVuZ2xlLCBleGNlcHRpb25hbGx5IHRhbGwgdHJlZXMgZ3JvdyB0aGF0IHN1cHBvcnQgYSByaWNoIGJpb3NwaGVyZSBvZiBmaWdzIGFuZCBqdW5pcGVyIGJ1Z3MsIHdoaWNoIGhhcHBlbiB0byBiZSB0aGUgY3VsaW5hcnkgZGVsaWdodCBvZiBicm93biBtb25rZXlzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5SZWFjaGluZyB0aGUgY2Fub3B5IG9mIHRoZXNlIHRyZWVzIHJlcXVpcmVzIHRoZSBtb25rZXlzIHRvIHBlcmZvcm0gY2FyZWZ1bCBuYXZpZ2F0aW9uIHRocm91Z2ggdGhlIHRhbGwgdHJlZSZyc3F1bztzIGZyYWdpbGUgdmluZSBzeXN0ZW0uIFRoZXNlIHZpbmVzIG9wZXJhdGUgbGlrZSBhIHNlZS1zYXc6IGFuIHVuYmFsYW5jaW5nIG9mIHdlaWdodCBhdCBhbnkgdmluZSBqdW5jdGlvbiB3b3VsZCBzbmFwIHRoZSB2aW5lIGZyb20gdGhlIHRyZWUsIGFuZCB0aGUgbW9ua2V5cyB3b3VsZCBwbHVtbWV0IHRvIHRoZSBncm91bmQgYmVsb3cuIFRoZSBtb25rZXlzIGhhdmUgZmlndXJlZCBvdXQgdGhhdCBpZiB0aGV5IHdvcmsgdG9nZXRoZXIgdG8ga2VlcCB0aGUgdmluZXMgcHJvcGVybHkgYmFsYW5jZWQsIHRoZXkgY2FuIGFsbCBmZWFzdCBvbiB0aGUgZmlncyBhbmQganVuaXBlciBidWdzIGluIHRoZSBjYW5vcHkgb2YgdGhlIHRyZWVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIHZpbmUganVuY3Rpb24gc3VwcG9ydHMgZXhhY3RseSB0d28gc3ViLXZpbmVzLCBlYWNoIG9mIHdoaWNoIG11c3QgY29udGFpbiB0aGUgc2FtZSBudW1iZXIgb2YgbW9ua2V5cywgb3IgZWxzZSB0aGUgdmluZSB3aWxsIGJyZWFrLCBsZWF2aW5nIGEgcGlsZSBvZiBkZWFkIG1vbmtleXMgb24gdGhlIGp1bmdsZSBncm91bmQuIEZvciBwdXJwb3NlcyBvZiB0aGlzIHByb2JsZW0sIGEgdmluZSBqdW5jdGlvbiBpcyBkZW5vdGVkIGJ5IGEgcGFpciBvZiBtYXRjaGluZyBzcXVhcmUgYnJhY2tldHMgWyBdLCB3aGljaCBtYXkgY29udGFpbiBuZXN0ZWQgaW5mb3JtYXRpb24gYWJvdXQganVuY3Rpb25zIGZ1cnRoZXIgZG93biBpdHMgc3ViLXZpbmVzLiBUaGUgbmVzdGluZyBvZiB2aW5lcyB3aWxsIGdvIG5vIGZ1cnRoZXIgdGhhbiAyNSBsZXZlbHMgZGVlcC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvdXBsb2FkXC9pbWFnZXNcL21vbmtleS5wbmdcIiBzdHlsZT1cImhlaWdodDoyOTRweDsgd2lkdGg6NTIwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbWluaW11bSBudW1iZXIgb2YgbW9ua2V5cyByZXF1aXJlZCB0byBiYWxhbmNlIGEgcGFydGljdWxhciB2aW5lIGNvbmZpZ3VyYXRpb24uIFRoZXJlIGlzIGFsd2F5cyBhdCBsZWFzdCBvbmUgbW9ua2V5IG5lZWRlZCwgYW5kLCBtdWx0aXBsZSBtb25rZXlzIG1heSBoYW5nIGZyb20gdGhlIHNhbWUgdmluZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgTiwgKDEgJmxlOyBOICZsZTsgMTAwMCkgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhc2V0cyB0aGF0IGZvbGxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBkYXRhc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgb2YgaW5wdXQgY29udGFpbmluZyBhIHZpbmUgY29uZmlndXJhdGlvbiBjb25zaXN0aW5nIG9mIGEgc3RyaW5nIG9mIFsgYW5kIF0gY2hhcmFjdGVycyBhcyBkZXNjcmliZWQgYWJvdmUuIFRoZSBsZW5ndGggb2YgdGhlIHN0cmluZyBvZiBbIGFuZCBdIHdpbGwgYmUgZ3JlYXRlciB0aGFuIG9yIGVxdWFsIHRvIHplcm8sIGFuZCBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMTUwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIHlvdSBzaG91bGQgZ2VuZXJhdGUgb25lIGxpbmUgb2Ygb3V0cHV0IHdpdGggdGhlIGZvbGxvd2luZyB2YWx1ZXM6IFRoZSBtaW5pbXVtIG51bWJlciBvZiBtb25rZXlzIHJlcXVpcmVkIHRvIHJlYWNoIHRoZSBjYW5vcHkgc3VjY2Vzc2Z1bGx5LiBBc3N1bWUgdGhhdCBhbGwgdGhlIGhhbmdpbmcgdmluZXMgYXJlIHJlYWNoYWJsZSBmcm9tIHRoZSBqdW5nbGUgZmxvb3IsIGFuZCB0aGF0IGFsbCBtb25rZXlzIGp1bXAgb24gdGhlIHZpbmVzIGF0IHRoZSBzYW1lIHRpbWUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPk5vdGU6IFRoZSBzZWNvbmQgbGluZSBvZiBzYW1wbGUgaW5wdXQgaXMgYSBibGFuayBsaW5lLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > North America > Greater New York Region > 2007 Greater New York Programming Contest F번