Description
Benson, the manager of the park, is trying to assign the jobs to his workers. There are N workers and N different kinds of jobs. Each of the workers is able to, with various length of time required, finish a few kinds of jobs, but each of them must concentrate on finishing a single job and should not help with other jobs even if her or his own job is done.
They all start their work right after the jobs are assigned, so the time to call it a day depends on the latest ones who finish their jobs. The manager, and of course all of the workers, wish to go home as early as possible, so please help him to figure out a way to assign the jobs, with the restriction that each job is done by exactly one person and each person works on exactly one job, such that the latest finished job can be done as early as possible.
Input
The first line of the input is an integer Z (Z ≤ 10), which means the number of test cases that follows.
For each test case, the first line contains an integer N (N ≤ 100), which is the number of workers and jobs. Each of the next N lines contains N integers, where the j-th integer on the i-th line is the number of units of time for the i-th worker to finish the j-th kind of job, or -1 if the i-th worker should never work on the j-th kind of job. It is guaranteed that there is at least one possible assignment for each test case in the input.
There will be a leading blank line for each test case in the input.
Output
For each test case, output a line containing the test case number (starting from 1) and an integer, which is the minimum number of units of time to call it a day. The detailed format is shown in the sample output, and note that there is a single space character before the sharp sign and after the colon.