Freeform Factory (Large)

You have just built a brand new factory. It 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. You were in a hurry when you hired them, so you did not check whether they actually know how to operate your machines. Now you have finally asked them, and you know, for each i and j, 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. When a 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. A knows how to operate 1 and 2, and B knows how to operate 1 but not 2. If B arrives first, he picks machine 1. When A arrives, she has to choose 2, and the factory works well. However, if A arrives first, she might choose machine 1 that day. Then B has nothing to do when he arrives, machine 2 has no operator, and the factory wastes a whole day.

As another example, suppose there are two workers A and B and two machines 1 and 2. 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 the factory, you can teach your workers how to operate machines so that the factory is guaranteed to function well every day. Giving one worker a lesson on how to operate one machine costs one dollar. Each lesson involves only one worker and only one machine, but you can give any number of lessons to any number of workers, and the same worker can receive several 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. Then every machine is guaranteed to have an operator every day, regardless of the order in which the workers arrive and which machine each of them picks when there is more than one possibility.

What is the minimum number of dollars you need to spend on training 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 a line containing an integer N, the number of workers (and machines). It is followed by N lines, each a string of N characters. The j-th character of 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 25$

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 statement.

In sample case #3, nobody knows how to do 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 needed. 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 and make A the only worker who can operate that machine. B might then take either machine 1 or machine 2 on arrival, so C must be able to operate whichever one B did not take. Therefore C must be taught to operate both 1 and 2.