C. Too Much Walking
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a grid $$$a$$$ of $$$n$$$ rows and $$$n$$$ columns. The cell at the $$$i$$$-th row and $$$j$$$-th column of the grid is denoted by $$$a_{i,j}$$$.

The 3D manhattan distance between two cells $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is defined as $$$|a_{x_1,y_1}-a_{x_2,y_2}|+|x_1-x_2|+|y_1-y_2|$$$. Here, $$$|p|$$$ denotes the absolute value of $$$p$$$.

The maximum walking distance of a cell $$$(x,y)$$$ is the maximum 3D manhattan distance between the cell $$$(x,y)$$$ and all other cells $$$(i,j) \ (1 \leq i,j \leq n)$$$ in the grid.

Your task is to print the sum of the maximum walking distances of all cells in the grid.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — the number of test cases.

The first line of each test case contains one integer $$$n$$$ $$$(1 \leq n \leq 1000)$$$ — the dimension of the grid.

The following $$$n$$$ lines contain $$$n$$$ integers each; the $$$j$$$-th element in the $$$i$$$-th line $$$a_{i,j}$$$ is the number written in the $$$j$$$-th cell of the $$$i$$$-th row $$$(0 \leq a_{i,j} \leq 10^{9})$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, print the sum of the maximum walking distances of all cells in the grid.

Example
Input
2
2
2 6
4 5
5
3 9 2 0 10
4 7 1 5 5
15 3 3 0 0
5 5 5 3 10
8 4 13 1 5
Output
19
385
Note

In the first test case, for cell $$$(1,1)$$$:

  • 3D manhattan distance between $$$(1,1)$$$ and $$$(1,1) = |2-2|+|1-1|+|1-1| = 0$$$
  • 3D manhattan distance between $$$(1,1)$$$ and $$$(1,2) = |2-6|+|1-1|+|1-2| = 5$$$
  • 3D manhattan distance between $$$(1,1)$$$ and $$$(2,1) = |2-4|+|1-2|+|1-1| = 3$$$
  • 3D manhattan distance between $$$(1,1)$$$ and $$$(2,2) = |2-5|+|1-2|+|1-2| = 5$$$

So the maximum walking distance of cell $$$(1,1) = \operatorname{max}(\{0,5,3,5\}) = 5$$$

Similarly,

The maximum walking distance of cell $$$(1,2) = \operatorname{max}(\{5,0,4,2\}) = 5$$$

The maximum walking distance of cell $$$(2,1) = \operatorname{max}(\{3,4,0,2\}) = 4$$$

The maximum walking distance of cell $$$(2,2) = \operatorname{max}(\{5,2,2,0\}) = 5$$$

So, the sum of the maximum walking distances $$$=5+5+4+5=19$$$