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} < 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. 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). For each test case, output the minimum number of times Sakurako will have to use her magic so that all lakes disappear.