화학 분석

큐리오시티 탐사선은 화성 표면을 현장에서 분석하기 위해 다양한 첨단 장비를 싣고 있다. (화성의 암석을 지구로 가져오는 것은 상상하기 어렵다.) 과학자들이 시료에 어떤 화학 원소가 들어 있는지 추정하는 한 가지 방법은, 시료를 가열하거나 태워서 어떤 진동수의 빛이 방출되는지 관찰하는 것이다. 원소마다 고유한 스펙트럼이 있으므로, 관찰된 스펙트럼으로부터 어떤 원소들의 조합이 그것을 만들어 냈는지 추론할 수 있다.

이를 다음과 같이 모형화한다. 가능한 진동수는 $n$개이고 ($1 \le n \le 100$), 후보 원소는 $m$개이다 ($1 \le m \le 12$). 각 후보 원소는 어떤 진동수에서 빛을 방출하는지를 나타내는 길이 $n$의 0과 1로 이루어진 벡터로 주어진다. 시료도 같은 형식의 길이 $n$ 벡터로 주어진다.

원소가 시료에 조금이라도 들어 있으면, 그 원소가 방출하는 모든 진동수가 관찰된다고 가정한다. 여러 원소가 같은 진동수를 방출하더라도 그 진동수는 한 번만 관찰되며, 서로 상쇄되는 일은 없다. 따라서 어떤 원소들의 집합이 시료를 설명한다는 것은, 그 원소들이 방출하는 진동수들의 합집합이 시료의 스펙트럼과 정확히 일치한다는 뜻이다. 즉 선택한 원소가 방출하는 모든 진동수는 시료에 나타나야 하고, 관찰된 모든 진동수는 선택한 원소 중 적어도 하나가 방출해야 한다.

각 시료에 대해, 합쳐진 스펙트럼이 관찰된 스펙트럼과 정확히 일치하는 원소의 최소 개수를 구하여라. 그런 조합이 없으면 없다고 보고하여라.

첫 줄에는 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 두 정수 $n$과 $m$이 주어진다. 각각 진동수의 개수와 원소의 개수이다.

다음 $m$개의 줄에는 각각 하나의 원소를 나타내는 길이 $n$의 0과 1로 이루어진 문자열이 주어진다 ($i$번째 줄은 $i$번째 원소를 나타낸다). 그다음 줄에는 시료를 나타내는 길이 $n$의 0과 1로 이루어진 문자열이 주어진다.

각 데이터 집합에 대해, 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 그 데이터 집합의 번호이다(1부터 시작). 다음 줄에는 합쳐진 스펙트럼이 관찰된 스펙트럼과 정확히 일치하는 원소의 최소 개수를 출력한다. 관찰된 스펙트럼을 정확히 만들어 내는 원소 조합이 없으면 대신 Impossible을 출력한다. 연속한 데이터 집합 사이에는 빈 줄을 하나 출력한다.