D. Матричный каскад
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана матрица размера $$$n \times n$$$, состоящая из 0 и 1. Строки матрицы пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, столбцы пронумерованы от $$$1$$$ до $$$n$$$ слева направо. Клетку на пересечении $$$x$$$-й строки и $$$y$$$-го столбца обозначим как $$$(x, y)$$$.

AquaMoon хочет превратить все элементы матрицы в 0. За один шаг она может выполнить следующую операцию:

  • выбрать произвольную клетку, пусть это $$$(i, j)$$$, затем инвертировать элемент в клетке $$$(i, j)$$$, а также инвертировать все элементы в клетках $$$(x, y)$$$, для которых $$$x > i$$$ и $$$x - i \ge \left|y - j\right|$$$. Инвертирование — это замена символа на противоположный: 0 на 1, 1 на 0.

Помогите AquaMoon определить наименьшее число шагов, необходимых для того, чтобы превратить все элементы матрицы в 0. Можно показать, что ответ всегда существует.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 3000$$$).

В $$$i$$$-й из следующих $$$n$$$ строк содержится бинарная строка, состоящая только из символов 0 и 1, имеющая длину $$$n$$$.

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$9\,000\,000$$$.

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

Для каждого набора входных данных выведите наименьшее необходимое число шагов.

Пример
Входные данные
3
5
00100
01110
11111
11111
11111
3
100
110
110
6
010101
111101
011110
000000
111010
001110
Выходные данные
1
2
15
Примечание

В первом наборе входных данных можно действовать так:

  1. выполнить операцию для клетки $$$(1, 3)$$$.

Очевидно, изначально не все элементы матрицы равны 0, так что необходима как минимум одна операция. Значит, $$$1$$$ и есть ответ.

В втором наборе входных данных можно действовать так:

  1. выполнить операцию для клетки $$$(3, 3)$$$;
  2. выполнить операцию для клетки $$$(1, 1)$$$.

Можно показать, что невозможно превратить все элементы в 0 за $$$0$$$ шагов или за $$$1$$$ шаг, так что ответ равен $$$2$$$.