Details
The selection consists of N parts, and there are N machines available. Each machine can manufacture any part. For each machine and part, the time t[i, k] required to manufacture the k-th part on the i-th machine is provided.
Your task is to write a program that determines the optimal machine assignment for each part so that, when all parts begin manufacturing simultaneously, they are all completed in the shortest possible time.
Input
The first line of the input contains the number of test cases. For each test case, the first line contains the number of machines and parts N (1 ≤ N ≤ 50). The next N lines list the manufacturing times for each part on the corresponding machine, given as t[i,1], t[i,2], ..., t[i,N], separated by commas. Each time is a natural number not exceeding 100.
The input data is guaranteed to be correct.
Output
For each test case, output a single line listing the part numbers that should be manufactured on the 1-st, 2-nd, ..., N-th machines, separated by spaces. On the following line, output the total time from the start to the completion of all parts.
For each test case, finding one valid solution is sufficient.