As is known to all, LL’s brain is composed of N parts, which can think about N problems individually and simultaneously. Today LL is very tired, but he is stilled faced with N problems, so he decides to use each part to think about one problem once and go to bed. LL knows how much time it costs for part i of his brain to work out problem j. Now he wants to know how to assign problem to his brain to work out all problems as soon as possible. Of course this problem is a small dish for LL, but solving only one problem using the whole brain is what a waste for LL, so you are asked to solve it…
Input
The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer N, the number of parts LL brain has (1 <= N <= 200). Then next N lines each contains N numbers. The jth number of the ith line is the time needed by ith part to solve the jth problem. Each time is in range [1, 10000].
Output
For each case, output a line containing the minimum time required to work out all problems.