During her journey with Kosuke, Sakurako and Kosuke found a valley that can be represented as a matrix of size $$$n \times n$$$, where at the intersection of the $$$i$$$-th row and the $$$j$$$-th column is a mountain with a height of $$$a_{i,j}$$$. If $$$a_{i,j} \lt 0$$$, then there is a lake there.

Kosuke is very afraid of water, so Sakurako needs to help him:

With her magic, she can select a square area of mountains and increase the height of each mountain on the main diagonal of that area by exactly one.

More formally, she can choose a submatrix with the upper left corner located at $$$(i, j)$$$ and the lower right corner at $$$(p, q)$$$, such that $$$p-i=q-j$$$. She can then add one to each element at the intersection of the $$$(i + k)$$$-th row and the $$$(j + k)$$$-th column, for all $$$k$$$ such that $$$0 \le k \le p-i$$$.

Determine the minimum number of times Sakurako must use her magic so that there are no lakes.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 200$$$) — the number of test cases.

Each test case is described as follows:

The first line of each test case consists of a single number $$$n$$$ ($$$1 \le n \le 500$$$).
Each of the following $$$n$$$ lines consists of $$$n$$$ integers separated by spaces, which correspond to the heights of the mountains in the valley $$$a$$$ ($$$-10^5 \le a_{i,j} \le 10^5$$$).

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

Output

For each test case, output the minimum number of times Sakurako will have to use her magic so that all lakes disappear.

Sakurako and Water

Examples