Hanging Monkeys

Deep in the jungle, monkeys climb fragile vines to reach the figs at the top of very tall trees.

Some vines split into two branches and behave like a seesaw. If the two branches do not carry the same number of monkeys, the vine breaks and the monkeys fall. By cooperating, the monkeys can keep every split balanced.

A vine is written with square brackets. An empty string means a vine with no split and requires one monkey. A pair of brackets [...] means one split. The two child vines are written consecutively inside the brackets, and either child may be empty. At every split, the two child vines must receive the same number of monkeys. A child may receive more monkeys than its own minimum requirement if that is needed to balance its sibling.

The depth of the vine is at most 25.

For each vine, find the minimum number of monkeys that can reach the top while keeping every split balanced.

The first line contains the number of test cases N (1 <= N <= 1000).

Each test case is given on one line as a square-bracket representation of a vine. The string length is at least 0 and less than 150. A blank test case is represented by an empty line.

For each test case, print the minimum number of monkeys needed to reach the top while keeping the vine balanced.

An empty vine has no split, so its answer is 1.