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 ith 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.
Large I/O files. Please consider using fast input/output methods.
## Input
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 ith row of the array. Array values are between 1 and 500.
## Output
For each test case, print one line containing one integer, the answer to the problem.
[samples]
## Note
Large I/O files. Please consider using fast input/output methods.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case, let $ N \in \mathbb{Z} $ be the dimension of a square matrix $ A \in \mathbb{Z}^{N \times N} $, where $ 1 \leq A[i][j] \leq 500 $ for all $ i, j \in \{1, \dots, N\} $.
Let $ \mathcal{R} $ be the set of all axis-aligned sub-rectangles of $ A $, defined by their top-left corner $ (R_1, C_1) $ and bottom-right corner $ (R_2, C_2) $, where $ 1 \leq R_1 \leq R_2 \leq N $ and $ 1 \leq C_1 \leq C_2 \leq N $.
For a rectangle $ R = \{(i,j) \mid R_1 \leq i \leq R_2,\ C_1 \leq j \leq C_2\} $, define:
- $ \text{MAX}(R) = \max_{i=R_1}^{R_2} \max_{j=C_1}^{C_2} A[i][j] $
- $ \text{MIN}(R) = \min_{i=R_1}^{R_2} \min_{j=C_1}^{C_2} A[i][j] $
**Constraints**
1. $ 1 \leq T \leq \text{large} $
2. For each test case: $ 1 \leq N \leq 500 $
3. $ 1 \leq A[i][j] \leq 500 $ for all $ i, j \in \{1, \dots, N\} $
**Objective**
For each test case, compute:
$$
\sum_{R \in \mathcal{R}} \left( \text{MAX}(R) - \text{MIN}(R) \right)
$$