B. Сакурако и вода
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время своего похода с Косукэ, Сакурако и Косукэ нашли долину, которую можно представить в виде матрицы $$$n \times n$$$, где на пересечении $$$i$$$-й строки и $$$j$$$-го столбца находится гора высотой $$$a_{i,j}$$$. Если $$$a_{i,j} < 0$$$, то там находится озеро.

Косукэ очень боится воды, поэтому Сакурако нужно помочь ему:

  • С помощью своей магии она может выбрать квадратный участок гор и увеличить высоту каждой горы на главной диагонали этого участка ровно на один.

Более формально, она может выбрать подматрицу с верхним левым углом, расположенным в $$$(i, j)$$$, и нижним правым углом в $$$(p, q)$$$, так что $$$p-i=q-j$$$. И добавить один к каждому элементу на пересечении $$$(i + k)$$$-й строки и $$$(j + k)$$$-го столбца, для всех $$$k$$$, где $$$0 \le k \le p-i$$$.

Определите минимальное количество раз, которое Сакурако должна использовать свою магию, чтобы все озера исчезли.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 200$$$) — количество наборов входных данных.

Каждый набор входных данных описывается следующим образом:

  • первая строка каждого набора входных данных состоит из одного числа $$$n$$$ ($$$1 \le n \le 500$$$)
  • каждая из следующих $$$n$$$ строк состоит из $$$n$$$ целых чисел, разделенных пробелами, которые соответствуют высоте гор в матрице $$$a$$$ ($$$-10^5 \le a_{i,j} \le 10^5$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$1000$$$.

Выходные данные

Для каждого теста выведите минимальное количество раз, которое Сакурако придется использовать свою магию, чтобы все озера исчезли.

Пример
Входные данные
4
1
1
2
-1 2
3 0
3
1 2 3
-2 1 -1
0 0 -1
5
1 1 -1 -1 3
-3 1 4 4 -4
-1 -1 3 0 -5
4 5 3 -3 -1
3 1 -3 -1 5
Выходные данные
0
1
4
19