平衡挂饰（mobile）是一种利用平衡原理制作的动态雕塑。它由若干根吊杆组成，吊杆上悬挂着有重量的物体或其他吊杆。悬挂在吊杆上的物体相互平衡，使得吊杆基本保持水平。每根吊杆仅由一根绳子悬挂，这使得它可以绕着绳子自由旋转。

我们考虑这样一种平衡挂饰：每根吊杆都恰好在其正中间与悬挂它的绳子相连，如下图所示。现在给你一个这样的配置，但末端的重量选择得不正确，导致挂饰无法处于平衡状态。由于这不够美观，你决定修改其中一些重量。

要使挂饰达到平衡，你最少需要修改多少个重量？你可以将任何重量替换为任意（可能是非整数的）重量。对于图中所示的挂饰，可以通过将中间的重量从 7 修改为 3 来达到平衡，因此只需要修改 1 个重量。

输入格式

第一行包含一个正整数：测试用例的数量，最多为 100。接下来对于每个测试用例：

• 一行，包含挂饰的结构，这是一个递归定义的表达式，格式如下：

  $$\langle expr \rangle ::= \langle weight \rangle \mid \text{"["} \langle expr \rangle \text{","} \langle expr \rangle \text{"]"}$$

  其中 $\langle weight \rangle$ 是一个小于 $10^9$ 的正整数，表示一个重量；$[\langle expr \rangle, \langle expr \rangle]$ 表示一根吊杆，其两端连接着这两个表达式。从任意一个重量到挂饰顶部的路径中，吊杆的总数最多为 16。

输出格式

对于每个测试用例：

• 输出一行，包含必须修改的最小重量个数。

样例

输入样例 1

3
[[3,7],6]
40
[[2,3],[4,5]]

输出样例 1

1
0
3