자유 배정 공장 (Small)

새 공장을 막 지었다. 공장에는 서로 다른 기계가 $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만 운전할 줄 알며 B는 아무것도 운전할 줄 모른다고 하자. 이 경우 작업자가 어떤 순서로 도착하든 공장은 제대로 돌아갈 수 없다.

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

예를 들어 위의 두 예시는 모두 작업자 B에게 기계 2의 운전법을 가르치면 해결된다. 그러면 작업자가 어떤 순서로 도착하든, 고를 기계가 여럿일 때 어느 기계를 고르든 매일 모든 기계에 운전자가 생긴다.

공장이 매일 제대로 돌아가도록 하기 위해 작업자 교육에 써야 하는 최소 금액(달러)은 얼마인가?

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

제한

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

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