在本题中，我们考虑一种称为布尔树的二叉树。在这棵树中，除了最后一层（最深层）外，每一层都是完全填满的，且最后一层的节点尽可能靠左。此外，树中的每个节点要么有 0 个子节点，要么有 2 个子节点。

布尔树的特殊之处在于每个节点都有一个与之关联的布尔值（0 或 1）。此外，每个内部节点都有一个“与”（AND）门或“或”（OR）门。与门节点的值由其两个子节点值的逻辑与运算给出。或门节点的值由其两个子节点值的逻辑或运算给出。所有叶节点的值将在输入中给出，以便可以向上计算出所有节点的值。

我们对树的根节点特别感兴趣。我们非常希望根节点的值为 $V$（0 或 1）。遗憾的是，根节点当前的值可能并非如此。幸运的是，我们可以通过修改某些节点的门类型来作弊；我们可以将与门改为或门，或者将或门改为与门。

给定布尔树的描述以及哪些门可以修改，求出为了使根节点的值为 $V$ 所需修改的最少门数。如果无法实现，输出 "IMPOSSIBLE"。

输入格式

输入文件的第一行包含测试用例的数量 $N$。接下来是 $N$ 个测试用例。

每个测试用例以 $M$ 和 $V$ 开头。$M$ 表示树中节点的数量，且 $M$ 为奇数，以确保所有节点都有 0 或 2 个子节点。$V$ 是根节点的目标值，为 0 或 1。

接下来有 $M$ 行描述树的每个节点。第 $X$ 行描述节点 $X$，从第一行的节点 1 开始。

前 $(M-1)/2$ 行描述内部节点。每行包含 $G$ 和 $C$，均为 0 或 1。如果 $G$ 为 1，则该节点的门是与门，否则是或门。如果 $C$ 为 1，则该节点的门可以修改，否则不可修改。内部节点 $X$ 的子节点为 $2X$ 和 $2X+1$。

接下来的 $(M+1)/2$ 行描述叶节点。每行包含一个值 $I$（0 或 1），即叶节点的值。

为了便于理解，这里是第一个样例输入中树的图片。

输出格式

对于每个测试用例，输出：

Case #$X$: $Y$

其中 $X$ 是测试用例的编号，$Y$ 是为了使根节点输出为 $V$ 所需修改的最少门数，如果无法实现，则输出 "IMPOSSIBLE"。

数据范围

$1 < N \le 20$

小数据集（测试集 1 - 可见；5 分）

$2 < M < 30$

大数据集（测试集 2 - 隐藏；10 分）

$2 < M < 10000$

样例

输入 1

2
9 1
1 0
1 1
1 1
0 0
1
0
1
0
1
5 0
1 1
0 0
1
1
0

输出 1

Case #1: 1
Case #2: IMPOSSIBLE

说明

在样例 1 中，我们可以将节点 3 的门改为或门，从而在根节点处达到预期的结果。

在样例 2 中，只有根节点可以修改，但将其改为或门并不能解决问题。