Chemical Analysis

The Curiosity rover carries a lot of high-tech hardware so it can analyze the Martian surface on the spot. (Sending rocks back from Mars is hard to imagine.) One way scientists infer which chemical elements are present in a sample is to heat or burn it and observe which frequencies of light are emitted. Each element has a characteristic spectrum, so from the observed spectrum one can work out which combination of elements could have produced it.

We model this as follows. There are $n$ possible frequencies ($1 \le n \le 100$) and $m$ candidate elements ($1 \le m \le 12$). Each candidate element is described by an $n$-bit vector of zeros and ones telling at which frequencies it emits light. The sample is described by the same kind of $n$-bit vector.

We assume that if an element occurs in the sample in any quantity, then every frequency it emits is observed. When several elements emit the same frequency, that frequency is still observed just once — there is no cancellation. Therefore a set of elements explains the sample exactly when the union of their emitted frequencies equals the sample's spectrum: every frequency an element emits must appear in the sample, and every observed frequency must be emitted by at least one chosen element.

For each sample, determine the smallest number of elements whose combined spectrum equals the observed spectrum, or report that no combination does.

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

The first line holds two integers $n$ and $m$: the number of frequencies and the number of elements.

The next $m$ lines each contain a string of $n$ ones and zeros describing one element (line $i$ describes element $i$). The following line contains a string of $n$ ones and zeros describing the sample.

For each data set, first print Data Set x: on its own line, where $x$ is the data set's number (starting from 1). On the next line print the minimum number of elements whose combined spectrum equals the observed spectrum. If no combination of elements produces exactly the observed spectrum, print Impossible instead. Separate consecutive data sets with a blank line.