계층형 민주주의

문제

데모크라티아 공화국의 대통령 선거는 여러 단계를 거쳐 진행된다.

대통령 후보는 정확히 두 명이다.
1단계에서 유권자는 자신이 속한 선거구의 투표소에서 투표한다. 그 선거구의 승자는 표를 과반수 얻은 후보다. 유권자가 직접 표를 던지는 단계는 1단계뿐이다.
$k > 1$ 인 $k$ 단계 선거구는 여러 개의 $k-1$ 단계 선거구로 이루어진다. 반대로 $k-1$ 단계 선거구는 오직 하나의 $k$ 단계 선거구에만 속한다. $k$ 단계 선거구의 승자는 그 선거구를 이루는 $k-1$ 단계 선거구 중 과반수에서 이긴 후보다.
마지막 단계에는 전국을 하나로 묶은 선거구가 하나뿐이다. 마지막 단계의 승자가 대통령이 된다.

이 나라의 선거는 다음 조건을 만족한다.

유권자는 모두 투표한다.
1단계 선거구마다 유권자 수가 홀수다.
$k > 1$ 일 때 $k$ 단계 선거구를 이루는 $k-1$ 단계 선거구의 개수도 홀수다.

그래서 모든 단계의 모든 선거구에서 승자가 한 명씩 정해지고, 동점은 나오지 않는다.

가장 적은 표로 대통령이 되는 방법을 찾아 그 표 수를 구하는 프로그램을 작성하라. 예를 들어 마지막 단계 선거구가 1단계 선거구 세 개로 이루어지고 각 선거구의 유권자 수가 123, 4567, 89라고 하자. 승자가 되는 데 필요한 최소 표는 107표다. 첫 번째 선거구에서 62표, 세 번째 선거구에서 45표를 얻으면 된다. 이때 상대 후보가 두 번째 선거구의 4567표를 전부 가져가도 패배를 피하지 못한다. 이 제도가 불공평해 보이더라도 주어진 규칙 그대로 받아들이면 된다.

입력

입력 전체의 형태는 다음과 같다.

데이터셋의 개수 (= n)
1번째 데이터셋
2번째 데이터셋
...
n번째 데이터셋

데이터셋의 개수 $n$ 은 100 이하다.

각 선거구의 유권자 수와 선거구 사이의 포함 관계는 다음 표기법으로 적는다.

1단계 선거구는 [c]로 적는다. 여기서 $c$ 는 그 선거구의 유권자 수다.
$k > 1$ 인 $k$ 단계 선거구는 [d1d2...dm]으로 적는다. $d_1$ 부터 $d_m$ 까지는 그 선거구를 이루는 $k-1$ 단계 선거구를 같은 표기법으로 적은 문자열이다.

유권자가 123명인 1단계 선거구는 [123]으로 적는다. 유권자가 각각 123명, 4567명, 89명인 1단계 선거구 세 개로 이루어진 2단계 선거구는 [[123][4567][89]]로 적는다.

각 데이터셋은 마지막 단계 선거구를 위 표기법으로 적은 문자열 한 줄이다. 입력은 다음을 만족한다.

문자열은 숫자 0부터 9까지와 대괄호 [, ] 외의 문자를 포함하지 않고, 길이는 11 이상 10000 이하다.
1단계 선거구의 유권자 수는 3 이상 9999 이하다.

단계의 수는 전국이 같다. 그래서 [[[9][9][9]][9][9]] 같은 문자열은 입력에 나오지 않는다. 2단계 이후의 선거구는 이전 단계 선거구를 반드시 여러 개 포함하므로 [[[[9]]]]도 나오지 않는다.

출력

데이터셋마다 대통령 선거에서 승자가 되는 데 필요한 최소 표 수를 한 줄에 출력한다. 출력 줄에는 그 수를 적는 숫자 말고 다른 문자가 들어가면 안 된다.