Во время своего похода с Косукэ, Сакурако и Косукэ нашли долину, которую можно представить в виде матрицы \(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\).
Определите минимальное количество раз, которое Сакурако должна использовать свою магию, чтобы все озера исчезли.
Выходные данные
Для каждого теста выведите минимальное количество раз, которое Сакурако придется использовать свою магию, чтобы все озера исчезли.