Hierarchical Democracy

The presidential election of the Republic of Democratia runs in several stages.

1. There are exactly two presidential candidates.
2. At the first stage, every eligible voter votes at the poll of his or her own electoral district. The winner of a district is the candidate who takes a majority of the votes cast there. Voters cast ballots only at this first stage.
3. A district of stage $k$, where $k > 1$, consists of several districts of stage $k-1$. Conversely, a district of stage $k-1$ belongs to exactly one district of stage $k$. The winner of a stage $k$ district is the candidate who wins a majority of its stage $k-1$ sub-districts.
4. The final stage has a single nation-wide district. Its winner becomes the president.

You may assume the following about this election.

• Every eligible voter casts a vote.
• The number of eligible voters in each first-stage district is odd.
• For $k > 1$, the number of stage $k-1$ sub-districts that form a stage $k$ district is also odd.

Every district of every stage therefore has exactly one winner, and no tie occurs.

Write a program that finds the smallest number of votes with which a candidate can win the election. Suppose the final-stage district consists of three first-stage districts whose numbers of eligible voters are 123, 4567 and 89. The minimum number of votes needed to win is 107, taking 62 votes in the first district and 45 in the third. Even if the other candidate took all 4567 votes of the second district, that candidate would still lose. The system may look unfair, but take it as given.

The whole input has this shape.

the number of datasets (= n)
1st dataset
2nd dataset
...
n-th dataset

The number of datasets $n$ is at most 100.

The number of eligible voters of each district and the part-whole relation among districts are written in the following notation.

• A first-stage electoral district is written as [c], where $c$ is the number of eligible voters of that district.
• A district of stage $k$, where $k > 1$, is written as [d1d2...dm], where $d_1$ through $d_m$ are its stage $k-1$ sub-districts written in the same notation.

A first-stage district with 123 eligible voters is written as [123]. A second-stage district made of three first-stage districts with 123, 4567 and 89 eligible voters is written as [[123][4567][89]].

Each dataset is one line holding the string that denotes the final-stage district in this notation. The input satisfies the following.

• The string contains no characters other than the digits 0 through 9 and the square brackets [ and ], and its length is between 11 and 10000, inclusive.
• The number of eligible voters of each first-stage district is between 3 and 9999, inclusive.

The number of stages is the same across the whole country, so a string such as [[[9][9][9]][9][9]] never appears in the input. A district of the second or a later stage always contains several districts of the previous stage, so [[[[9]]]] never appears either.

For each dataset, print in one line the minimum number of votes needed to win the presidential election. An output line must contain no characters other than the digits of that number.