Swing is opening a pancake factory! A good pancake factory must be good at flattening things, so Swing is going to test his new equipment on 2D matrices.

Swing is given an $n \times n$ matrix $M$ containing positive integers. He has $q$ queries to ask you.

For each query, he gives you four integers $x_1$, $y_1$, $x_2$, $y_2$ and asks you to flatten the submatrix bounded by $(x_1, y_1)$ and $(x_2, y_2)$ into an array $A$. Formally, $A = [M_{(x1,y1)}, M_{(x1,y1+1)}, \ldots, M_{(x1,y2)}, M_{(x1+1,y1)}, M_{(x1+1,y1+1)}, \ldots, M_{(x2,y2)}]$.

The following image depicts the flattening of a submatrix bounded by the red dotted lines. The orange arrows denote the direction that the elements of the submatrix are appended to the back of $A$, and $A$ is shown at the bottom of the image.

Afterwards, he asks you for the value of $\sum_{i=1}^{|A|} A_i \cdot i$ (sum of $A_i \cdot i$ over all $i$).

Input

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

The first line of each test contains two integers $n$ and $q$ ($1 \leq n \leq 2000, 1 \leq q \leq 10^6$) — the length of $M$ and the number of queries.

The following $n$ lines contain $n$ integers each, the $i$'th of which contains $M_{(i,1)}, M_{(i,2)}, \ldots, M_{(i,n)}$ ($1 \leq M_{(i, j)} \leq 10^6$).

The following $q$ lines contain four integers $x_1$, $y_1$, $x_2$, and $y_2$ ($1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq n$) — the bounds of the query.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$ and the sum of $q$ over all test cases does not exceed $10^6$.

Output

For each test case, output the results of the $q$ queries on a new line.

见题面 Input 部分

见题面 Output 部分

In the second query of the first test case, $A = [9, 5, 5, 2]$. Therefore, the sum is $1 \cdot 9 + 2 \cdot 5 + 3 \cdot 5 + 4 \cdot 2 = 42$.