Problem D: Ranking

To encourage healthy student teacher interaction, Mumbai School Board requires each school in Mumbai to make every student in the school play 20 decisive games of chess (draws are not counted) with each teacher in the school each year. Thus every teacher (numbered sequentially from 1 to n) at the end of the year has an integer score which is an even number between -20 (if he lost all 20 decisive games) to +20 (if he won all decisive games) against each student (numbered sequentially from 1 to m). The school submits a 2 dimensional (n rows, m columns, n,m less than 100000) matrix of such teacher scores to the Board every year.

The Board then computes an overall evaluation for each school in the following way. It picks some k (less or equal to n) adjacent rows (i.e k teachers numbered consecutively). For each teacher $t_i$ who is picked a weight $w_i$ is generated by picking any $j_i$ (less or equal to m) consecutive students from his row of scores and summing his scores against them. Note that this is done independently for each teacher- that is the number of consecutive students picked may be different for different teachers. The School's overall evaluation is the sum of the weights of these k teachers.

You have to write a program for the Board which will take the data for many schools one by one and compute the lowest possible evaluation for each school.

Input

The first line gives the number of schools. Then for each school, the first line gives the number of teachers (n) and students (m) in this school (2 numbers separated by space). This is followed by n lines (one per teacher) of scores. Each line has m numbers (separated by one space) which is the scores of that teacher against each of the m students. The data for School 1 is followed (immediately without any blank lines) by data for School 2 and so on.

Output

Output is one line per school (without any blank lines inbetween) containing one number which is the minimum possible score for that school.

Sample Input

2
2 4
10 -4 -4 10
-4  2 -8 4
2 6
0 -6 4 -6 -4 4
2  2 2  2  2 2

Sample Output

-18
-12