Arsenic and Old Lace

Many murder mysteries — in movies, and even in real life — involve a victim who is poisoned by an evil mixture of chemicals, herbs, radioactive materials, or other things. A key clue for finding the murderer is discovering which rare substances were used. For instance, if the poison came from poison dart frogs, then the murderer or an accomplice must have been in South or Central America recently. But this requires working out the individual substances that were mixed together.

To do this, the police can rely on an analysis of the poison that lists all of its individual substances. They also have a catalogue of base products, each with its own list of individual substances. The question is then: what is the smallest number of base products that could have been combined to account for exactly the individual substances found in the victim?

The first line contains the number $K$ of data sets. Then follow the $K$ data sets, each of the following form.

The first line of a data set contains two integers $s$ and $b$: the number of individual substances $1 \le s \le 50$ and the number of base products $1 \le b \le 20$. The next $b$ lines each describe one base product as a string of $s$ characters. The $i$-th character is y if the base product contains individual substance $i$, and n otherwise. One final line describes the poison found in the victim in the same way.

For each data set, output the line Data Set x: on its own, where $x$ is the data set's number. On the next line, output the minimum number of base products that together provide all of the individual substances in the poison and none other. If no such combination exists, output Impossible. instead. Separate consecutive data sets with a blank line.