Omar Loves Candies

Omar loves eating a lot of candy, but unfortunately most candy is not healthy. His parents therefore gave every candy a score. A higher score means a healthier candy, and a score is an integer that can be positive, zero or negative.

One day Omar went shopping for candy with his parents and they found a strange store. The store lays its candy out in a grid of $N$ rows with $M$ candies in each row. Rows are numbered $1$ to $N$ from top to bottom, columns are numbered $1$ to $M$ from left to right, and every cell holds one candy.

The display follows a rule. Every candy outside the first row has a higher score than the candy directly above it, and every candy outside the first column has a higher score than the candy directly to its left.

There is only one way to buy candy here: pick a sub-rectangle of the grid and buy every candy inside it. A sub-rectangle is the set of cells shared by a block of consecutive rows $r_1$ through $r_2$ and a block of consecutive columns $c_1$ through $c_2$ ($1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le M$). A group of candies with any other shape cannot be picked.

Omar's parents want the non-empty sub-rectangle whose candy scores add up to the largest possible total. Find that total.

The first line contains one integer $T$, the number of test cases ($1 \le T \le 100$).

Each test case begins with a line holding two integers separated by a single space, $N$ and $M$ ($1 \le N, M \le 1000$), the dimensions of the candy grid. The next $N$ lines each contain the $M$ scores of one row, separated by single spaces. The grid satisfies the rule above, and every score is an integer between $-2000$ and $2000$ inclusive.

For each test case, print one line with the largest score sum reachable from a non-empty sub-rectangle.