자유형 공장

당신은 방금 완전히 새로운 공장을 지었다. 공장에는 서로 다른 N대의 기계가 있으며, 공장이 제대로 가동되려면 각 기계를 정확히 한 명의 작업자가 조작해야 한다.

당신은 이 기계들을 조작할 N명의 작업자도 고용했다. 이들을 서둘러 고용했기 때문에, 이들이 실제로 당신의 기계를 조작할 줄 아는지는 확인하지 않았다. 이제 마침내 이들에게 물어보았고, 각 i와 j에 대해 i번째 작업자가 j번째 기계를 조작할 수 있는지에 관한 정보를 얻었다.

일반적인 근무일에 작업자들은 무작위 순서로 공장에 도착하며, 이 순서는 날마다 달라질 수 있다. 각 작업자는 도착하면 자신이 조작할 줄 알고 아직 조작자가 없는 모든 기계를 찾는다. 그중 하나를 무작위로 골라 근무일 내내 조작한다. 자신이 조작할 줄 아는 모든 기계에 이미 조작자가 있다면 그날은 일하지 않는다. 당신의 목표는 작업자들이 어떤 순서로 도착하고 어떤 기계를 고르든 상관없이 매 근무일에 모든 기계가 조작되도록 보장하는 것이다.

예를 들어 작업자 A와 B 두 명, 그리고 기계 1와 2 두 대가 있다고 하자. A는 1와 2를 조작할 줄 알고, B는 1를 조작할 줄 알지만 2는 조작할 줄 모른다고 하자. 작업자 B가 먼저 도착하면 기계 1를 고르고, 이후 작업자 A가 도착하면 2를 골라야 하므로 공장은 제대로 가동된다. 그러나 작업자 A가 먼저 도착하면 그날 1를 조작하기로 고를 수도 있으며, 그러면 작업자 B가 도착했을 때 할 일이 없어 기계 2에는 조작자가 남지 않고, 공장은 하루 전체를 낭비하게 된다!

또 다른 예로 작업자 A와 B 두 명, 기계 1와 2 두 대가 있고, A는 1를 조작할 줄 알지만 2는 조작할 줄 모르며, B는 어떤 것도 조작할 줄 모른다고 하자. 그러면 작업자들이 어떤 순서로 도착하든 공장은 제대로 가동될 수 없다.

공장을 열기 전에 공장이 항상 제대로 가동되도록 보장하기 위해 작업자들에게 기계 조작법을 가르칠 수 있다. 작업자 한 명에게 기계 한 대의 조작법을 한 번 가르치는 데 한 달러가 든다. 각 교육에는 작업자 한 명과 기계 한 대만 포함되지만, 원하는 수의 작업자에게 원하는 만큼 교육할 수 있으며 같은 작업자가 여러 번 교육받을 수도 있다. 작업자가 이미 조작할 줄 아는 기계의 조작법을 잊게 만들 수는 없다.

예를 들어 위의 두 예는 모두 작업자 B에게 기계 2의 조작법을 가르치면 해결할 수 있다. 이 경우 작업자들이 어떤 순서로 도착하고, 조작할 수 있는 기계가 하나보다 많을 때 어떤 기계를 고르든 상관없이 매일 각 기계에 조작자가 있음이 보장된다.

공장이 매일 제대로 가동되도록 하기 위해 작업자 교육에 지출해야 하는 최소 금액은 몇 달러인가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ N ≤ 4.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ 25.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 작업자 수이자 기계 수인 정수 N이 있는 한 줄로 시작한다. 그 뒤에는 각각 N개의 문자로 이루어진 문자열이 있는 N개의 줄이 이어진다. 이 줄들 중 i번째 줄의 j번째 문자는 i번째 작업자가 j번째 기계를 조작할 줄 알면 1이고, 그렇지 않으면 0이다.

각 테스트 케이스마다 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 모두의 조작법을 가르쳐야 한다.