405367: GYM101915 L Eyb0ss

PinkGuy is a 5-star Popstar in America and Japan. Known for his songs about self-motivation , fighting against racism and poverty. 50 Percent of his albums profit goes to charity. He's working now on releasing his new album "eyb0ss". He promised his friend wheelz that he is going to finish this album , before wheelz gets his new car. However, he is still in college and doesn't have much time to focus on his studies. He recently got an assignment , and he needs you to do it for him.

Given a 2D array N * N.Each cell is denoted by 2 integers Cell(R, C). R denoting the number of its row. C denoting the number of its column. The rows are numbered from 1 to N from top to down. The columns are numbered form 1 to N left to right.

Consider every sub-rectangle of this array. Each rectangle is identified by 2 cells Rectangle({R1, C1}, {R2, C2}) . {R1, C1} denoting its upper-left corner , {R2, C2} denoting its lower-right corner. A single cell is considered a rectangle.

You are asked to calculate the following sum :

MAX(R1, C1, R2, C2) is a function returns the maximum integer in the Rectangle ({R1, C1}, {R2, C2}).

MIN(R1, C1, R2, C2) is a function returns the minimum integer in the Rectangle ({R1, C1}, {R2, C2}).

The first line contains a single integer T, the number of test cases. The first line of each test case contains a single integer N. (1 ≤ N ≤ 500). The following N lines each contains N integers, the values of the i^th row of the array. Array values are between 1 and 500.

For each test case, print one line containing one integer, the answer to the problem.

3
2
1 3
5 10
3
1 1 1
1 1 1
1 1 1
3
1 8 1
2 4 9
2 4 5

27
0
131

Large I/O files. Please consider using fast input/output methods.