원숭이 매달기

깊은 정글의 거대한 나무 꼭대기에는 원숭이들이 좋아하는 무화과가 열린다. 원숭이들은 꼭대기까지 올라가기 위해 부서지기 쉬운 덩굴을 조심해서 타야 한다.

어떤 덩굴은 두 갈래로 나뉘며, 시소처럼 균형을 이룬다. 두 갈래에 매달린 원숭이 수가 서로 다르면 덩굴이 끊어져 원숭이들이 떨어진다. 원숭이들은 서로 협력해서 모든 분기의 균형을 맞출 수 있다.

덩굴 구조는 대괄호로 나타낸다. 빈 문자열은 분기가 없는 덩굴을 뜻하며, 이 경우 원숭이 한 마리가 필요하다. 대괄호 한 쌍 [...]은 하나의 분기점을 뜻한다. 괄호 안에는 두 하위 덩굴이 차례로 쓰이며, 어느 한쪽 하위 덩굴이 비어 있을 수 있다. 각 분기점에서는 두 하위 덩굴에 같은 수의 원숭이를 보내야 한다. 한 하위 덩굴이 자체적으로 필요한 최소 수보다 더 많은 원숭이를 받아도, 다른 하위 덩굴과 균형을 맞출 수 있다면 괜찮다.

덩굴의 깊이는 25를 넘지 않는다.

각 덩굴에 대해, 모든 분기의 균형을 유지하면서 나무 꼭대기에 도달할 수 있는 최소 원숭이 수를 구하라.

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

각 테스트 케이스는 한 줄로 주어지며, 덩굴 구조를 대괄호로 표현한 문자열이다. 문자열의 길이는 0 이상 150 미만이다. 빈 테스트 케이스는 빈 줄로 주어진다.

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

빈 덩굴은 분기가 없으므로 정답은 1이다.