Biomedical Engineering

Biomedical engineering tries to use biological phenomena to engineer drugs or other substances at a very small scale. When designing a new drug, an important aspect is to make it attach to the right receptor cells in the body, where it triggers or inhibits certain reactions. The underlying biology can be very complex, so we work with the following simplified model.

A docking site is described by a string $z$ of $n$ letters, giving the chemical properties at $n$ consecutive locations. We want to assemble a matching string out of given primitive components so that it attaches at the site. We are given $m$ component strings $y_1, y_2, \dots, y_m$, where each $y_i$ consists of $n_i$ letters. The goal is to choose a sequence of these components whose concatenation is exactly equal to $z$. The supply of every component is unlimited, so any $y_i$ may be used arbitrarily many times.

The first line contains an integer $K \ge 1$, the number of data sets. Each data set has the following form:

• The first line contains the integer $m$ ($1 \le m \le 100$), the number of available component strings.
• The second line contains the string $z$ ($1 \le |z| \le 1000$), consisting only of uppercase and lowercase English letters.
• Each of the next $m$ lines contains one component string $y_i$ ($1 \le |y_i| \le 1000$), consisting only of uppercase and lowercase English letters.

String matching is case-sensitive.

For each data set, first print Data Set x: on a line by itself, where $x$ is the data set number, starting from $1$. On the next line, print the minimum number of components whose concatenation equals $z$. If $z$ cannot be assembled from the components, print Impossible instead.