Freeform Factory (Small)

You have just built a brand new factory. Your factory has $N$ different machines, and each machine needs to be operated by exactly one worker for the factory to function well.

You have also hired $N$ workers to operate those machines. Since you were in a hurry when you hired them, you did not check whether they actually know how to operate your machines. Now you have finally asked them, so for each $i$ and $j$ you know whether the $i$-th worker can operate the $j$-th machine.

On a typical working day, the workers arrive at the factory in a random order, which can be different each day. As each worker arrives, they find all machines that they know how to operate and that do not already have an operator. They choose one of those at random and operate it for the whole working day. If every machine they know how to operate already has an operator, they do not work that day. Your goal is to make sure that all machines are operated every working day, regardless of the order in which the workers arrive and which machines they choose.

For example, suppose there are two workers A and B, and two machines 1 and 2. Suppose that A knows how to operate 1 and 2, and B knows how to operate 1 but not 2. If worker B arrives first, he picks machine 1; then when worker A arrives she has to choose 2, and the factory works well. However, if worker A arrives first, she might choose to operate 1 on that day. Then when worker B arrives he has nothing to do, machine 2 is left without an operator, and your factory wastes a whole day.

As another example, suppose there are two workers A and B, and two machines 1 and 2, and that A knows how to operate 1 but not 2, and B does not know how to operate anything. Then, regardless of the order in which the workers arrive, the factory cannot function well.

Before you open your factory, you can teach your workers how to operate machines, so that the factory is guaranteed to always function well. It costs one dollar to give a single worker a lesson on how to operate a single machine. Each lesson involves only one worker and only one machine, but you can teach any number of lessons to any number of workers, and the same worker can receive multiple lessons. You cannot make a worker forget how to operate a machine they already know.

For example, both examples above can be fixed by teaching worker B to operate machine 2. In that case each machine is guaranteed to have an operator every day, regardless of the order in which the workers arrive and which machines they choose when they have more than one option.

What is the minimum number of dollars you need to spend on training workers so that the factory functions well every day?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with one line containing an integer $N$, the number of workers (and machines). This line is followed by $N$ lines, each containing a string of $N$ characters. The $j$-th character on the $i$-th of those lines is 1 if the $i$-th worker knows how to operate the $j$-th machine, and 0 otherwise.

Limits

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

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a non-negative integer: the minimum number of dollars you need to spend so that all $N$ machines always have an operator.

Sample cases #1 and #2 are the ones described in the problem statement.

In sample case #3, nobody knows how to operate anything. One optimal strategy is to teach worker A to operate machine 1, worker B to operate machine 2, and worker C to operate machine 3.

In sample case #4, no action is necessary. There is only one worker, and that worker already knows how to operate the only machine.

In sample case #5, worker B already knows how to operate machines 1 and 2. One optimal strategy is to teach worker A to operate machine 3, making A the only worker who can operate that machine. But B might operate either machine 1 or machine 2 upon arrival, so C needs to be able to operate whichever one B did not choose. So C must be taught to operate both 1 and 2.