C. Уголки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана таблица из $$$n$$$ строк и $$$m$$$ столбцов, в каждой клетке которой записано число $$$0$$$ или число $$$1$$$.

Уголком будем называть любой квадратик $$$2 \times 2$$$ без одной угловой клетки. Вы хотите добиться того, что в таблице не останется ни одной единицы. За одну операцию вы можете выбрать любой уголок, который содержит хотя бы одну $$$1$$$, и заменить все числа в уголке на нули.

Вам очень нравится ваша таблица, поэтому вы хотите определить, какое максимальное количество операций вы можете сделать перед тем, как в таблице останутся лишь нули.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных находятся два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n, m \leq 500$$$) — размеры таблицы.

В каждой из следующих $$$n$$$ строк бинарная строка длины $$$m$$$ — описание таблицы.

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

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

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

Пример
Входные данные
4
4 3
101
111
011
110
3 4
1110
0111
0111
2 2
00
00
2 2
11
11
Выходные данные
8
9
0
2
Примечание

В первом тестовом случае одним из возможных способов оптимально выполнить операции является следующий (жирным шрифтом выделяется треугольник, на котором была выполнена операция):

  • Матрица до выполнения каких либо операций:
    101
    111
    011
    110
  • Матрица после выполнения $$$1$$$ операции:
    100
    101
    011
    110
  • Матрица после выполнения $$$2$$$ операций:
    100
    100
    011
    110
  • Матрица после выполнения $$$3$$$ операций:
    100
    100
    010
    110
  • Матрица после выполнения $$$4$$$ операций:
    100
    000
    010
    110
  • Матрица после выполнения $$$5$$$ операций:
    100
    000
    010
    100
  • Матрица после выполнения $$$6$$$ операций:
    100
    000
    000
    100
  • Матрица после выполнения $$$7$$$ операций:
    000
    000
    000
    100
  • Матрица после выполнения $$$8$$$ операций:
    000
    000
    000
    000

В третьем тестовом случае из примера мы не можем выполнить ни одной операции, так как в изначальной таблице нет единиц.

В четвертом тестовом случае из примера вне зависимости от выбора первого уголка у нас всегда останется единственная единичка. Поэтому всего мы применим $$$2$$$ операции.