시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 333 74 52 31.138%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3
[]

[[][[]]]

예제 출력 1

2
1
8

힌트

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

W3sicHJvYmxlbV9pZCI6IjI3MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDBcdWMyMmRcdWM3NzQgXHViOWU0XHViMmVjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWFlNGFcdWM3NDAgXHVjNTQ0XHViOWM4XHVjODc0IFx1YzgxNVx1YWUwMFx1YzVkMCBcdWFjNzBcdWIzMDBcdWQ1NWMgXHViMDk4XHViYjM0XHViNGU0XHVjNWQwXHVjMTFjIFx1YWMwOFx1YzBjOSBcdWM2ZDBcdWMyMmRcdWM3NzRcdWI0ZTRcdWM3NzQgXHViOWU0XHVjNmIwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWJiMzRcdWQ2NTRcdWFjZmNcdWFjMDAgXHVjNWY0XHViOWFjXHVhY2UwLCBcdWM3NzQgXHViMDk4XHViYjM0XHVjNWQwXHViMjk0IFx1ZDVhNVx1YjA5OFx1YmIzNFx1YjE3OFx1YjliMFx1YzdhY1x1YjRlNFx1Yzc3NCBcdWMxMWNcdWMyZGRcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIwOThcdWJiMzQgXHVhZjJkXHViMzAwXHVhZTMwXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjNmQwXHVjMjJkXHVjNzc0XHViNGU0XHVjNzQwIFx1YjllNFx1YzZiMCBcdWM4NzBcdWMyZWNcdWMyYTRcdWI3ZmRcdWFjOGMgXHViMDk4XHViYjM0XHVjNWQwIFx1YzYyY1x1Yjc3Y1x1YWMwMFx1YjI5NCBcdWFlMzhcdWM3NDQgXHVjYzNlXHVjNTQ0XHVjNTdjXHVkNTVjXHViMmU0LiBcdWFjNzBcdWIzMDBcdWQ1NWMgXHViMDk4XHViYjM0XHViMjk0IFx1YmQ4MFx1YzExY1x1YzljMFx1YWUzMCBcdWMyNmNcdWM2YjQgXHViMzY5XHVhZDc0XHViNGU0XHVjNzc0IFx1Yzc4OFx1YjI5NFx1YjM3MCBcdWM3NzQgXHViMzY5XHVhZDc0XHViNGU0XHVjNzQwIFx1YzJkY1x1YzE4Y1x1Yzc1OCBcdWM2ZDBcdWI5YWNcdWM2NDAgXHViZTQ0XHVjMmI3XHVkNTU4XHViMmU0LiBcdWIzNjlcdWFkNzRcdWM3NTggXHViYjM0XHVhYzhjXHVhYzAwIFx1YmQ4OFx1YWRlMFx1ZDYxNSBcdWQ1NThcdWJhNzQgXHVhZGY4IFx1YjM2OVx1YWQ3NFx1Yzc0MCBcdWIwNGFcdWM1YjRcdWM5YzBcdWJhNzAgXHVhZGY4IFx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWI1NDVcdWM3M2NcdWI4NWMgXHViNWE4XHVjNWI0XHVjODM4XHViYzg0XHViOWIwXHViMmU0LiBcdWM2ZDBcdWMyMmRcdWM3NzRcdWI0ZTRcdWM3NDAgXHVjMTFjXHViODVjIFx1ZDYxMVx1YjgyNVx1ZDU1OFx1YzVlYyBcdWIzNjlcdWFkNzRcdWM3NTggXHVhZGUwXHVkNjE1XHVjNzQ0IFx1YzcyMFx1YzljMFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWFkZjhcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIFx1YmIzNFx1ZDY1NFx1YWNmY1x1YWMwMCBcdWM1ZjRcdWI5YWNcdWFjZTAgXHVkNWE1XHViMDk4XHViYjM0XHViMTc4XHViOWIwXHVjN2FjXHViNGU0XHVjNzc0IFx1YzExY1x1YzJkZFx1ZDU1OFx1YjI5NCBcdWIwOThcdWJiMzQgXHVhZjJkXHViMzAwXHVhZTMwXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjM2OVx1YWQ3NFx1Yzc0MCBcdWI0NTBcdWFjMWNcdWM3NTggXHViMzY5XHVhZDc0XHViODVjIFx1YjA5OFx1YjIyMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwIFx1YjM2OVx1YWQ3NFx1Yzc3NCBcdWIwNGFcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWIwOThcdWIyMjBcdWM5YzQgXHViNDUwIFx1YjM2OVx1YWQ3NFx1Yzc0MCBcdWFjMTlcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc3NCBcdWI5ZTRcdWIyZWNcdWI4MjQgXHVjNzg4XHVjNWI0XHVjNTdjXHVkNTVjXHViMmU0LiBcdWIzNjlcdWFkNzRcdWM3NTggXHViMDk4XHViMjIwXHVjOWMwXHViMjk0IFx1YzljMFx1YzgxMFx1Yzc0NCAmcXVvdDtbXSZxdW90O1x1Yjg1YyBcdWM4MTVcdWM3NTggXHViMGI0XHViOWFjXHViYTc0IFx1YjM2OVx1YWQ3NFx1Yzc1OCBcdWFkNmNcdWM4NzBcdWI5N2MgXHVhZWJlXHVjMWUwXHVhZDA0XHVkNjM4XHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHViMzY5XHVhZDc0XHVjNzU4IFx1YWU0YVx1Yzc3NFx1YjI5NCAyNVx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21vbmtleS5wbmdcIiBzdHlsZT1cIndpZHRoOiA1MjBweDsgaGVpZ2h0OiAyOTRweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNmQwXHVjMjJkXHVjNzc0XHViNGU0XHVjNzQwIFx1YjM2OVx1YWQ3NFx1Yzc1OCBcdWFkZTBcdWQ2MTVcdWM3NDQgXHVjNzIwXHVjOWMwXHVkNTU4XHViYTc0XHVjMTFjIFx1YjA5OFx1YmIzNFx1YWYyZFx1YjMwMFx1YWUzMFx1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVjNmQwXHVjMjJkXHVjNzc0IFx1YzIxOFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWIwOThcdWJiMzQgXHVhZjJkXHViMzAwXHVhZTMwXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjZDVjXHVjMThjIFx1ZDU1YyBcdWI5YzhcdWI5YWMgXHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggTigxICZsZTsgTiAmbGU7IDEwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWIzNjlcdWFkNzRcdWM3NTggXHVhZDZjXHVjODcwXHViOTdjIFx1YWViZVx1YzFlMFx1YWQwNFx1ZDYzOFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDE1MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjM2OVx1YWQ3NFx1Yzc1OCBcdWFkZTBcdWQ2MTVcdWM3NDQgXHVjNzIwXHVjOWMwXHVkNTU4XHViYTc0XHVjMTFjIFx1YjA5OFx1YmIzNFx1YWYyZFx1YjMwMFx1YWUzMFx1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVjNmQwXHVjMjJkXHVjNzc0IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdFx1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjVcdWM3NTggMlx1YmM4OFx1YzlmOCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YmU0OCBcdWM5MDQgXHVjNzg1XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjcxNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1vbmtleSBWaW5lcyIsImRlc2NyaXB0aW9uIjoiPHA+RGVlcCBpbiB0aGUgQW1hem9uIGp1bmdsZSwgZXhjZXB0aW9uYWxseSB0YWxsIHRyZWVzIGdyb3cgdGhhdCBzdXBwb3J0IGEgcmljaCBiaW9zcGhlcmUgb2YgZmlncyBhbmQganVuaXBlciBidWdzLCB3aGljaCBoYXBwZW4gdG8gYmUgdGhlIGN1bGluYXJ5IGRlbGlnaHQgb2YgYnJvd24gbW9ua2V5cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+UmVhY2hpbmcgdGhlIGNhbm9weSBvZiB0aGVzZSB0cmVlcyByZXF1aXJlcyB0aGUgbW9ua2V5cyB0byBwZXJmb3JtIGNhcmVmdWwgbmF2aWdhdGlvbiB0aHJvdWdoIHRoZSB0YWxsIHRyZWUmcnNxdW87cyBmcmFnaWxlIHZpbmUgc3lzdGVtLiBUaGVzZSB2aW5lcyBvcGVyYXRlIGxpa2UgYSBzZWUtc2F3OiBhbiB1bmJhbGFuY2luZyBvZiB3ZWlnaHQgYXQgYW55IHZpbmUganVuY3Rpb24gd291bGQgc25hcCB0aGUgdmluZSBmcm9tIHRoZSB0cmVlLCBhbmQgdGhlIG1vbmtleXMgd291bGQgcGx1bW1ldCB0byB0aGUgZ3JvdW5kIGJlbG93LiBUaGUgbW9ua2V5cyBoYXZlIGZpZ3VyZWQgb3V0IHRoYXQgaWYgdGhleSB3b3JrIHRvZ2V0aGVyIHRvIGtlZXAgdGhlIHZpbmVzIHByb3Blcmx5IGJhbGFuY2VkLCB0aGV5IGNhbiBhbGwgZmVhc3Qgb24gdGhlIGZpZ3MgYW5kIGp1bmlwZXIgYnVncyBpbiB0aGUgY2Fub3B5IG9mIHRoZSB0cmVlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSB2aW5lIGp1bmN0aW9uIHN1cHBvcnRzIGV4YWN0bHkgdHdvIHN1Yi12aW5lcywgZWFjaCBvZiB3aGljaCBtdXN0IGNvbnRhaW4gdGhlIHNhbWUgbnVtYmVyIG9mIG1vbmtleXMsIG9yIGVsc2UgdGhlIHZpbmUgd2lsbCBicmVhaywgbGVhdmluZyBhIHBpbGUgb2YgZGVhZCBtb25rZXlzIG9uIHRoZSBqdW5nbGUgZ3JvdW5kLiBGb3IgcHVycG9zZXMgb2YgdGhpcyBwcm9ibGVtLCBhIHZpbmUganVuY3Rpb24gaXMgZGVub3RlZCBieSBhIHBhaXIgb2YgbWF0Y2hpbmcgc3F1YXJlIGJyYWNrZXRzIFsgXSwgd2hpY2ggbWF5IGNvbnRhaW4gbmVzdGVkIGluZm9ybWF0aW9uIGFib3V0IGp1bmN0aW9ucyBmdXJ0aGVyIGRvd24gaXRzIHN1Yi12aW5lcy4gVGhlIG5lc3Rpbmcgb2YgdmluZXMgd2lsbCBnbyBubyBmdXJ0aGVyIHRoYW4gMjUgbGV2ZWxzIGRlZXAuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbW9ua2V5LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI5NHB4OyB3aWR0aDo1MjBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3Ugd2lsbCB3cml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtb25rZXlzIHJlcXVpcmVkIHRvIGJhbGFuY2UgYSBwYXJ0aWN1bGFyIHZpbmUgY29uZmlndXJhdGlvbi4gVGhlcmUgaXMgYWx3YXlzIGF0IGxlYXN0IG9uZSBtb25rZXkgbmVlZGVkLCBhbmQsIG11bHRpcGxlIG1vbmtleXMgbWF5IGhhbmcgZnJvbSB0aGUgc2FtZSB2aW5lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBOLCAoMSAmbGU7IE4gJmxlOyAxMDAwKSB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGFzZXRzIHRoYXQgZm9sbG93LiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGRhdGFzZXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBvZiBpbnB1dCBjb250YWluaW5nIGEgdmluZSBjb25maWd1cmF0aW9uIGNvbnNpc3Rpbmcgb2YgYSBzdHJpbmcgb2YgWyBhbmQgXSBjaGFyYWN0ZXJzIGFzIGRlc2NyaWJlZCBhYm92ZS4gVGhlIGxlbmd0aCBvZiB0aGUgc3RyaW5nIG9mIFsgYW5kIF0gd2lsbCBiZSBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gemVybywgYW5kIGxlc3MgdGhhbiBvciBlcXVhbCB0byAxNTAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YXNldCwgeW91IHNob3VsZCBnZW5lcmF0ZSBvbmUgbGluZSBvZiBvdXRwdXQgd2l0aCB0aGUgZm9sbG93aW5nIHZhbHVlczogVGhlIGRhdGFzZXQgbnVtYmVyIGFzIGEgZGVjaW1hbCBpbnRlZ2VyIChzdGFydCBjb3VudGluZyBhdCBvbmUpLCBhIHNwYWNlLCBhbmQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vbmtleXMgcmVxdWlyZWQgdG8gcmVhY2ggdGhlIGNhbm9weSBzdWNjZXNzZnVsbHkuIEFzc3VtZSB0aGF0IGFsbCB0aGUgaGFuZ2luZyB2aW5lcyBhcmUgcmVhY2hhYmxlIGZyb20gdGhlIGp1bmdsZSBmbG9vciwgYW5kIHRoYXQgYWxsIG1vbmtleXMganVtcCBvbiB0aGUgdmluZXMgYXQgdGhlIHNhbWUgdGltZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+Tm90ZTogVGhlIHNlY29uZCBsaW5lIG9mIHNhbXBsZSBpbnB1dCBpcyBhIGJsYW5rIGxpbmUuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=