모빌

모빌은 평형(균형)의 원리를 이용해 만든 조각 작품이다. 모빌은 여러 개의 막대와 물체로 이루어진다. 물체는 막대의 양 끝에만 매달 수 있고, 막대 역시 실을 이용해 다른 막대의 끝에 매달 수 있다.

한 막대가 다른 막대에 매달릴 때는 항상 그 막대의 한가운데(중앙)가 위쪽 막대의 끝에 연결된다. 따라서 모든 막대는 자기 중앙에서 매달리며 양팔의 길이가 같다. 이때 막대가 균형을 이루려면 막대의 왼쪽 끝에 매달린 전체 무게와 오른쪽 끝에 매달린 전체 무게가 같아야 한다. 어떤 막대에 매달린 전체 무게란 그 아래에 달린 모든 물체의 무게를 더한 값이다.

모빌 전체는 모든 막대가 각각 균형을 이룰 때에만 균형을 이룬다. 균형을 이루지 못한 모빌이 주어졌을 때, 물체 몇 개의 무게를 바꾸면 모빌 전체가 균형을 이루는지, 그 최소 개수를 구하는 프로그램을 작성하시오.

물체의 무게는 음이 아닌 임의의 실수로 바꿀 수 있다. 예를 들어 어떤 막대의 한쪽 끝에는 무게가 각각 3과 7인 두 물체를 매단 막대가, 다른 쪽 끝에는 무게가 6인 물체가 매달려 있다고 하자. 무게가 7인 물체를 3으로 바꾸면 모든 막대가 균형을 이루므로, 물체 1개의 무게만 바꾸면 된다.

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스는 한 줄로 이루어지며, 다음과 같이 재귀적으로 표현된다.

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

여기서 <weight>는 $10^9$보다 작은 양의 정수로, 물체 하나의 무게를 나타낸다. [<expr>,<expr>]는 하나의 막대를 나타내며, 두 <expr>는 각각 그 막대의 왼쪽 끝과 오른쪽 끝에 매달린 것을 뜻한다. 가장 위에 있는 막대부터 가장 아래에 있는 막대까지, 한 표현에 중첩된 막대의 개수(두 막대 포함)는 최대 16개이다.

각 테스트 케이스마다 모빌이 균형을 이루도록 하기 위해 무게를 바꿔야 하는 물체의 최소 개수를 한 줄에 하나씩 출력한다.