비소와 낡은 레이스

많은 추리물에서는 — 영화뿐 아니라 실제 사건에서도 — 피해자가 화학 물질, 약초, 방사성 물질 등을 뒤섞은 사악한 혼합물에 중독되곤 한다. 범인을 찾는 실마리는 어떤 희귀 물질이 사용되었는지를 알아내는 것이다. 예를 들어 독이 독화살개구리에서 얻은 것이라면, 범인이나 공범은 최근에 남아메리카나 중앙아메리카에 다녀왔어야 한다. 하지만 이를 위해서는 혼합에 사용된 개별 물질들을 먼저 알아내야 한다.

이를 위해 경찰은 독에 대한 분석 결과, 즉 그 안에 들어 있는 모든 개별 물질의 목록을 활용할 수 있다. 또한 경찰은 여러 기초 제품과 각 제품에 들어 있는 개별 물질의 목록도 가지고 있다. 이때 궁금한 것은, 피해자에게서 발견된 개별 물질들을 정확히 설명하기 위해 조합할 수 있는 기초 제품의 최소 개수이다.

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

각 데이터 집합의 첫 번째 줄에는 두 정수 $s$와 $b$가 주어진다. $s$는 개별 물질의 수로 $1 \le s \le 50$이고, $b$는 기초 제품의 수로 $1 \le b \le 20$이다. 이어지는 $b$개의 줄은 각각 하나의 기초 제품을 길이 $s$의 문자열로 나타낸다. $i$번째 문자는 그 기초 제품이 개별 물질 $i$를 포함하면 y, 포함하지 않으면 n이다. 마지막 한 줄은 피해자에게서 발견된 독을 같은 방식으로 나타낸다.

각 데이터 집합마다, 먼저 그 집합의 번호를 $x$라 할 때 Data Set x: 를 한 줄에 출력한다. 다음 줄에는 독에 들어 있는 모든 개별 물질을 빠짐없이, 그리고 그 외의 물질은 하나도 포함하지 않도록 제공하는 기초 제품의 최소 개수를 출력한다. 그러한 조합이 존재하지 않으면 대신 Impossible. 을 출력한다. 연속한 두 데이터 집합 사이는 빈 줄로 구분한다.