Charging Chaos (Large)

Shota the farmer just moved into his newly built farmhouse, and the outlets there are not set up for his devices. He owns a pile of smartphones and laptops, and a tablet for his favorite cow Wagyu to use. In total he owns $N$ devices.

The devices have different specifications and come from different companies, so each one needs its own electric flow to charge. Each outlet also puts out one specific electric flow. An electric flow is a string of 0s and 1s of length $L$.

Shota wants to charge all $N$ devices at the same time, and his new house has exactly $N$ outlets. The flow from the outlets is configured on a master control panel with $L$ switches. Flipping switch $i$ flips the $i$-th bit of the flow from every outlet in the house.

For example, suppose three outlets put out 10, 01, and 11. Flipping the second switch turns those flows into 11, 00, and 10. If Shota has a smartphone that needs 11, a tablet that needs 10, and a laptop that needs 00, flipping the second switch alone charges all three.

Misaki measured the flow of every outlet in the house and found that they are all different. Decide whether Shota can charge all of his devices at the same time, and if he can, find the smallest number of switches that have to be flipped. The switches are big and heavy, so Misaki does not want to flip more of them than she has to.

The first line contains the number of test cases $T$. $T$ test cases follow, each on three lines.

The first line of a test case contains two integers $N$ and $L$ separated by a space. The second line contains $N$ strings of length $L$ separated by spaces, the flow that each outlet puts out at the start. The third line contains $N$ strings of length $L$ separated by spaces, the flow that each of Shota's devices needs.

Limits

• $1 \le T \le 100$
• $1 \le N \le 150$
• $2 \le L \le 40$
• No two outlets put out the same flow at the start.
• No two devices need the same flow.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the smallest number of switches that have to be flipped so that Shota can charge all of his devices. If there is no way to charge them all, print NOT POSSIBLE in place of $y$, without the quotes.

In the first test case of the first example, flipping the second switch once turns the outlet flows into 00, 10, and 11. Shota then charges device 1 from outlet 0, device 2 from outlet 1, and device 0 from outlet 2. Flipping nothing charges nothing, so 1 is the smallest answer.