마스터마인드: 최적의 다음 추측

마스터마인드는 두 명이 하는 게임이다. 첫 번째 사람인 출제자는 길이가 $l$인 코드를 비밀리에 정하는데, 각 글자는 대문자 A, B, C, ...(알파벳의 앞 $c$개 글자)로 나타내는 $c$가지 색 중 하나이다. 두 번째 사람인 추측자는 추측을 반복하여 이 코드를 알아내려 하며, 각 추측 역시 그런 글자 $l$개로 이루어진 문자열이다.

추측을 할 때마다 출제자는 검은 못과 흰 못을 이용해 두 개의 수를 알려 준다. 검은 못의 수는 색과 위치가 모두 맞은 자리의 개수이고, 흰 못의 수는 색은 코드 안에 있지만 위치가 다른, 남은 맞은 색의 개수이다. 예를 들어 비밀 코드가 ABCC이고 추측이 ACCD이면 응답은 검은 못 2개와 흰 못 1개이며, 추측이 CCAA이면 응답은 흰 못 3개이다. 추측자는 응답이 검은 못 $l$개가 될 때까지 계속 추측하는데, 이는 코드를 찾았다는 뜻이다.

이미 $n$번의 추측이 이루어지고 그 응답을 받았다고 하자. 어떤 코드가 이 $n$개의 응답 모두와 모순되지 않으면 그 코드는 여전히 가능한 코드이다. 다음에 할 후보 추측 하나를 생각하자. 이 후보는 여전히 가능한 코드만이 아니라 $c$가지 색으로 이루어진 길이 $l$의 아무 코드나 될 수 있다. 이 후보가 만들어 낼 수 있는 모든 응답을 생각하고, 각 응답마다 그 응답을 내놓을 가능한 코드가 몇 개인지 센다. 응답이 검은 못 $l$개라면 코드가 완전히 확정되므로 그 응답이 남기는 코드는 0개이다. 이 개수들 중 모든 응답에 대한 최댓값을 그 후보 추측의 불확실도라고 한다. 가장 좋은 다음 추측은 불확실도가 가장 작은 추측이다.

예를 들어 가능한 코드가 ABBB, ABBC, ABCB 세 개만 남았다고 하자. ABBB를 추측하면 응답은 두 가지이다: 검은 못 4개(코드를 찾음, 0개 남음) 또는 검은 못 3개(코드 2개가 남음, ABBC와 ABCB). 따라서 불확실도는 2이다. 대신 ABBC를 추측하면 응답은 세 가지이다: 검은 못 4개(0개 남음), 검은 못 3개(1개 남음, ABBB), 검은 못 2개와 흰 못 2개(1개 남음, ABCB). 따라서 불확실도는 1이다. 그러므로 이 경우에는 ABBC가 더 좋은 추측이다.

지금까지의 추측과 응답이 주어질 때, 가장 좋은 다음 추측을 구하는 프로그램을 작성하여라.

첫 줄에는 테스트 케이스의 수 $T$가 하나의 정수로 주어진다. 각 테스트 케이스는 여러 줄로 이루어진다. 첫 줄에는 세 정수 $l$, $c$, $n$이 주어지며, 각각 코드의 길이, 색의 수, 이미 이루어진 추측의 수를 나타낸다. $1 \le l \le 15$, $1 \le c \le 20$, $0 \le n \le 10$이다. $l$과 $c$는 항상 가능한 코드의 총 개수 $c^l$이 $32768$ 이하가 되도록 주어진다. 이어지는 $n$개의 줄은 각각 다음 형식이다.

guess b w

여기서 $guess$는 길이 $l$의 문자열이고, $b$와 $w$는 그 응답의 검은 못과 흰 못의 개수이다. 모든 색은 알파벳의 앞 $c$개 글자에서 뽑은 대문자이다. 각 테스트 케이스에서 주어진 추측들은 여전히 가능한 코드를 $1500$개 이하로 남긴다.

각 테스트 케이스마다, 가장 좋은 다음 추측과 그 불확실도를 하나의 공백으로 구분하여 한 줄에 출력한다. 불확실도가 가장 작은 추측이 여러 개이면, 사전순(알파벳순)으로 가장 앞선 것을 출력한다.