자유 형식 공장 (Large)

당신은 새 공장을 막 지었다. 공장에는 서로 다른 기계 N대가 있고, 공장이 제대로 돌아가려면 기계마다 정확히 한 명의 작업자가 그 기계를 운전해야 한다.

기계를 운전할 작업자도 N명 고용했다. 서둘러 고용하느라 이들이 실제로 기계를 다룰 줄 아는지는 확인하지 않았다. 이제야 물어본 결과, 모든 i와 j에 대해 i번째 작업자가 j번째 기계를 운전할 수 있는지 알고 있다.

평소 근무일에는 작업자들이 무작위 순서로 공장에 도착하며, 이 순서는 날마다 다를 수 있다. 작업자는 도착하면 자신이 운전할 줄 알면서 아직 운전자가 없는 기계를 모두 찾는다. 그중 하나를 무작위로 골라 그날 하루 종일 운전한다. 운전할 줄 아는 기계에 모두 이미 운전자가 있으면 그 작업자는 그날 일하지 않는다. 목표는 작업자의 도착 순서와 각자가 고르는 기계에 관계없이 모든 근무일에 모든 기계가 운전되도록 하는 것이다.

예를 들어 작업자 A와 B, 기계 1과 2가 있다고 하자. A는 1과 2를 모두 운전할 줄 알고, B는 1은 운전할 줄 알지만 2는 모른다. B가 먼저 도착하면 B는 기계 1을 고르고, 이어서 도착한 A는 2를 골라야 하므로 공장이 잘 돌아간다. 그러나 A가 먼저 도착하면 A가 그날 1을 고를 수도 있다. 그러면 나중에 도착한 B는 할 일이 없고 기계 2에는 운전자가 없어서, 공장은 하루를 통째로 날린다.

또 다른 예로 작업자 A와 B, 기계 1과 2가 있고, A는 1은 운전할 줄 알지만 2는 모르며 B는 아무 기계도 운전할 줄 모른다고 하자. 이 경우 작업자가 어떤 순서로 도착하든 공장은 제대로 돌아갈 수 없다.

공장이 항상 제대로 돌아가도록 보장하기 위해, 공장을 열기 전에 작업자에게 기계 운전법을 가르칠 수 있다. 작업자 한 명에게 기계 한 대의 운전법을 한 번 가르치는 데 1달러가 든다. 교육 한 번에는 작업자 한 명과 기계 한 대만 관여하지만, 교육은 몇 번이든 몇 명에게든 할 수 있고 같은 작업자가 여러 번 교육을 받을 수도 있다. 이미 운전할 줄 아는 기계를 작업자가 잊게 만들 수는 없다.

예를 들어 위의 두 예는 모두 작업자 B에게 기계 2의 운전법을 가르치면 해결된다. 그러면 작업자의 도착 순서와, 고를 수 있는 기계가 여럿일 때 각자가 고르는 기계에 관계없이 매일 모든 기계에 운전자가 있음이 보장된다.

공장이 매일 제대로 돌아가도록 하려면 교육에 최소 몇 달러를 써야 하는가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 작업자(그리고 기계)의 수 N이 주어진다. 다음 N개의 줄에는 각각 길이 N인 문자열이 주어진다. 그중 i번째 줄의 j번째 문자는 i번째 작업자가 j번째 기계를 운전할 줄 알면 1, 아니면 0이다.

제한

• $1 \le T \le 100$
• $1 \le N \le 25$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 N대의 기계 모두에 항상 운전자가 있도록 하기 위해 써야 하는 최소 금액(달러)으로, 음이 아닌 정수이다.

예제 케이스 #1과 #2는 문제 본문에서 설명한 경우이다.

예제 케이스 #3에서는 아무도 기계를 운전할 줄 모른다. 최적의 방법 중 하나는 작업자 A에게 기계 1, 작업자 B에게 기계 2, 작업자 C에게 기계 3의 운전법을 가르치는 것이다.

예제 케이스 #4에서는 아무것도 할 필요가 없다. 작업자가 한 명뿐이고, 그 작업자는 하나뿐인 기계를 이미 운전할 줄 안다.

예제 케이스 #5에서 작업자 B는 기계 1과 2를 이미 운전할 줄 안다. 최적의 방법 중 하나는 작업자 A에게 기계 3을 가르쳐서 A를 그 기계를 운전할 수 있는 유일한 작업자로 만드는 것이다. 그런데 B는 도착했을 때 기계 1과 2 중 어느 쪽이든 고를 수 있으므로, C는 B가 고르지 않은 기계를 운전할 수 있어야 한다. 따라서 C에게 1과 2를 모두 가르쳐야 한다.