Building Highways

Time Limit: 1 Second    Memory Limit: 32768 KB

As we all know, our country is now taking up with the development of the West Regions. Why the West Regions are far less developed than the other regions? The underdeveloped traffic and lack of knowledge are the main reasons.

Now, as a newly gratuated student from Zhejiang University, you are arranging a transaction for the highway state of one province of the West Regions. In this plan, there are certain locations that most people live in, and from each location there are paths that lead to other locations, but there are not necessarily paths that lead directly back. You are asked to guarantee that regardless of where someone in some location starts, there will be at least one path they can take that will return to their starting location. Now you are assigned the initial state of the highway condition. In order to behave your wisdom and efficience, you want to build the fewest highways to connect the locations and satisfy the request above. All highways are one-way. Note that you may build a highway that that starts and ends at the same location.

Input

The input file consist of a number of test cases. The first line of each test case contains a non-negative number n (n<=20) which indicates the number of the locations. The following n lines contain n numbers indicating relations between locations.The relationship will be expressed by '1' if there is a highway that leads directly from i to j, and a '0' if there is not a highway that leads directly from i to j. A negative N indicates the end of the test cases.

Output

First print the case number (counting from 1) in one line, then print the fewest highways you have to build in the other line. You should output a blank line between two cases.

Sample Input

5
0 0 1 0 1
0 0 0 1 0
0 0 0 1 0
1 0 0 0 0
0 0 0 0 0
-1

Sample Output

Test 1:
1

Submit

Source: ZOJ Monthly, January 2005