Mobile

A mobile is a sculpture built on the principle of balance. A mobile is made of several rods and objects. Objects may hang only from the two ends of a rod, and a rod may in turn hang, by a string, from the end of another rod.

When one rod hangs from another, it is always its exact center that is attached to the end of the rod above. Every rod is therefore suspended at its midpoint, so its two arms have equal length. For such a rod to balance, the total weight hanging from its left end must equal the total weight hanging from its right end. The total weight hanging from a rod is the sum of the weights of all objects below it.

The whole mobile is balanced only when every rod is individually balanced. Given a mobile that is not balanced, write a program that finds the minimum number of objects whose weight must be changed so that the entire mobile becomes balanced.

An object's weight may be changed to any non-negative real number. For example, suppose one end of a rod holds a smaller rod carrying two objects of weights 3 and 7, while the other end holds a single object of weight 6. Changing the object of weight 7 to weight 3 makes every rod balance, so changing just one object is enough.

The first line contains the number of test cases, which is at most 100.

Each test case consists of a single line, described recursively as follows.

<expr> ::= <weight> | "[" <expr> "," <expr> "]"

Here <weight> is a positive integer smaller than $10^9$ and denotes the weight of a single object. [<expr>,<expr>] denotes one rod, and the two <expr> values are what hang from the rod's left end and right end, respectively. Counting from the topmost rod down to the bottommost rod, the number of nested rods in one expression (including both of those rods) is at most 16.

For each test case, print on its own line the minimum number of objects whose weight must be changed so that the mobile becomes balanced.