Chemical Analysis

Curiosity is equipped with quite a lot of high-tech hardware in order to perform analysis of Mars surface in location. (It’s kind of hard to imagine sending rocks back from Mars.) One of the ways in which scientists try to infer which chemical elements are contained in a particular sample is to heat or burn them, and observe which frequencies of light are emitted. Different elements have characteristic spectra, and one can then see which combinations of elements would produce the observed spectrum.

We model this as follows: there are n possible frequencies, 1 ≤ n ≤ 100, and m elements that we suspect may occur on Mars (1 ≤ m ≤ 12). For each of the m elements that could possibly be in the sample, we are told at which frequencies they emit light: this is a bit vector of n zeros or ones. Similarly, the sample is described by such an n-bit vector. We assume that if element i occurs in the sample in any quantity, then all of its frequencies will be observed. If multiple elements produce the same frequency, we of course still observe that frequency — there is no cancellation. For each sample, you are to determine what is the smallest number of elements that would explain the observed spectrum, if any.

The first line contains the number K of data sets. This is followed by K data sets, each of the following form:

The first line contains two integers n,m, the number of frequencies and the number of elements.

This is followed by m + 1 lines. Line i for 1 ≤ i ≤ m describes the ith element, and is a string of n ones and zeros. Line m + 1 is a string of n ones and zeros describing the sample.

For each data set, output “Data Set x:” on a line by itself, where x is its number. Then output the minimum number of elements which together would produce the observed spectrum. If there is no such combination of elements, then output “Impossible” instead.