Cheating a Boolean Tree

A boolean tree is a kind of binary tree. It has an odd number of nodes numbered 1 through $M$. Nodes 1 through $(M-1)/2$ are internal nodes, and node $i$ has node $2i$ and node $2i+1$ as its children. Nodes $(M+1)/2$ through $M$ are leaf nodes.

Node values work like this. A leaf node holds 0 or 1. An internal node is either an AND gate or an OR gate. The picture below shows one boolean tree.

The value of a subtree follows directly. If the root of the subtree is a leaf node, the value of that leaf is the value of the subtree. If the root of the subtree is an internal node, the value of the subtree is what you get by combining the value of the left subtree and the value of the right subtree with that node's gate. For example, the subtree rooted at node 2 in the picture above has this value.

Val[2] = Val[4] AND Val[5] = (Val[8] OR Val[9]) AND 1 = (0 OR 1) AND 1 = 1

We want the value of the whole tree, that is Val[1], to be $V$. The value $V$ is 0 or 1 and comes from the input. The tree may currently evaluate to something else, so you are allowed to change the gate of some internal nodes. You can turn an AND gate into an OR gate and an OR gate into an AND gate. The nodes drawn in blue in the picture above are the ones you can change.

Given the boolean tree and which internal nodes you can change, find the minimum number of gates you have to change so that the whole tree evaluates to $V$.

The first line contains the number of test cases $T$ ($1 \le T \le 20$).

Each test case has this form.

• The first line contains $M$ and $V$. $M$ is the number of nodes of the boolean tree and is odd. $V$ is the value you want the whole tree to have. ($1 \le M \le 10000$, $V$ is 0 or 1)
• The next $(M-1)/2$ lines contain $a_i$ and $b_i$, the information of the internal nodes, in order starting from node 1. $a_i$ is the gate of that node, where 0 means an OR gate and 1 means an AND gate. $b_i$ tells whether the gate of that node can be changed: 1 means it can be changed, 0 means it cannot.
• The next $(M+1)/2$ lines contain $a_i$, the value of each leaf node, in order starting from node $(M+1)/2$.

For each test case, print one line in the form Case #c: x. Here $c$ is the test case number, counted from 1. $x$ is the minimum number of gates you have to change so that the whole tree evaluates to $V$. If no combination of gate changes makes the whole tree evaluate to $V$, print IMPOSSIBLE in place of $x$.