부호화된 통신

먼 거리로 — 사실 짧은 거리에서도 — 데이터를 전송하다 보면 보낸 비트가 우연히 뒤집히는 일이 생긴다. 이런 오류는 심각한 문제가 될 수 있다. 예를 들어 중요한 지시를 잘못 읽어 버릴 수도 있다. 이를 막기 위해 대부분의 장거리 통신과 무선 통신은 오류 정정 부호를 사용한다.

개념을 이해하기 위한 가장 간단한 예는 다음과 같다. 비트 하나 '0' 또는 '1'을 보내고 싶다면, 각각을 '000'과 '111'로 바꾸어 보낼 수 있다. 이렇게 하면 전송 도중 비트가 최대 한 개까지만 뒤집히더라도 수신자는 원래 비트가 '0'이었는지 '1'이었는지 여전히 알아낼 수 있다. 이렇게 단순히 복제하는 부호는 그다지 효율적이지 않으며, 추가 비트는 최대한 적게 쓰면서도 최대한 많은 비트 뒤집힘을 견디는 부호를 설계하는 것은 활발한 연구 주제다.

여기서는 훨씬 쉬운 문제를 푼다. 이미 누군가 설계해 놓은 부호와 수신된 부호어가 주어질 때, 전송 도중 몇 개의 비트가 뒤집혔어야 하는지를 알아내면 된다. 좀 더 구체적으로, 올바른 메시지가 될 수 있는 후보 문자열 $m_i$가 $1 \le n \le 1000$개 주어진다. 각 문자열은 0과 1로 이루어져 있으며 길이가 정확히 $b$비트이다($1 \le b \le 100$). 또한 수신된 메시지 $r$가 주어지며, 이 역시 길이 $b$비트의 0과 1 문자열이다. $r$의 비트를 몇 개 뒤집어야 어떤 $m_i$와 같아지는지, 그 최소 개수 $f$를 구하여라.

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

각 데이터 집합의 첫째 줄에는 두 정수 $n$과 $b$가 주어진다. 그 다음 $n$개의 줄에는 각각 하나의 올바른 부호어가 주어지며, 이는 0과 1로 이루어진 길이 $b$의 문자열이다. 이 $n$개의 줄 다음 줄에는 수신된 문자열 $r$가 주어지며, 역시 0과 1로 이루어진 길이 $b$의 문자열이다.

각 데이터 집합에 대해 한 줄에 Data Set x:를 출력한다. 여기서 $x$는 데이터 집합의 번호이며 1부터 시작한다. 다음 줄에는 수신된 문자열과 임의의 올바른 부호어 사이의 최소 거리 $f$를 출력한다. 연속한 데이터 집합 사이는 빈 줄 하나로 구분한다.