Jingle Balls

It is almost time to decorate the Christmas tree. The judges are already arguing about the best way to hang the balls, and they agree on one thing: the balls have to be spread evenly over the branches of the tree.

This problem is about binary Christmas trees. Such a tree starts as a trunk that splits into two subtrees. Each subtree may split again into two smaller subtrees, and so on. A subtree that does not split any further is a twig. A twig carries at most one ball.

A decorated tree has an even distribution of balls if and only if the following requirement holds.

At every point where a (sub)tree splits into two smaller subtrees $t_1$ and $t_2$, the number of balls in the left subtree $N(t_1)$ and the number of balls in the right subtree $N(t_2)$ are either equal or differ by exactly one. That is, $|N(t_1) - N(t_2)| \le 1$.

In their enthusiasm the judges first hang the balls on arbitrary twigs. When they run out of balls, they step back and look at the result. Most of the time the distribution is not even, so they decide to fix it by moving some of the balls to other twigs.

Given the structure of the tree and the initial positions of the balls, compute the minimum number of balls that have to be moved to reach an even distribution as defined above.

Adding new balls to the tree or taking balls off it for good is not allowed. The only way the tree may change is by moving balls to different twigs.

The input consists of several lines. Each line describes one decorated tree, and every line up to the end of the input has to be processed.

The description of a tree is a recursive description of its subtrees. A (sub)tree is written as a string in one of the following three forms.

• The string () is a twig without a ball.
• The string (B) is a twig with one ball attached to it.
• The string (t1t2) is a (sub)tree that splits into the two smaller subtrees t1 and t2. Both t1 and t2 are strings in one of these three forms, and there is no whitespace between the two descriptions.

A tree contains at least 2 and at most 1000 twigs.

Print one line for each tree.

If the balls can be distributed evenly, print the minimum number of balls that have to be moved to satisfy the requirement.

If the balls cannot be distributed evenly, print impossible.