\begin{problem}{Мадока и порванный фотоальбом}{стандартный ввод}{стандартный вывод}{1 секунда}{256 мегабайт}

Мадока недавно нашла свой фотоальбом из детского сада. И она хочет вырезать как можно больше из него фотографий, так как они ей не нравятся. Но при этом в нем есть фотки со своим любимым попугайчиком и она их никак не хочет трогать.

Фотоальбом представляет собой прямоугольник $n \times m$, где в каждой клетке содержится ровно одна фотография. Также для каждой фотографии известно, есть ли на ней попуг. Мадока может вырезать только подпрямоугольники фотоальбома. Но при том вырезанные подпрямоугольники не могут пересекаться или касаться по сторонам.

Так, например, следующие прямоугольники нельзя вырезать, так как они касаются по стороне:

\begin{center}
\includegraphics[width=50mm]{description.jpg}
\end{center}

Поэтому Мадоке стало интересно, а какое максимальное количество фотографий она может вырезать, соблюдая правила, и чтобы ни одна фотка с попугом не была вырезана.

\InputFile
Данная задача состоит из нескольких наборов тестовых случаев.

В первой строке задано единственное число $t$ ($1 \leq t \leq 3000$) --- количество тестовых случаев. Затем идет их описание.

В первой строке каждого тестового случая заданы два числа $n, m$ ($ 1 \leq n \leq 5, 1 \leq m \leq 10^4$).

Гарантируется, что сумма $m$ по всем тестовым случаям не превосходит $10^4$

Затем идут $n$ бинарных строк $a_1 a_2 \ldots a_m$, где равенство $a_j = 1$ означает, что в этой строке $j$-я фотография содержит попуга и ее нельзя вырезать.

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

\Example

\begin{example}
\exmpfile{example.01}{example.01.a}%
\end{example}

\Note
Примеры оптимальных ответов на семплы

\begin{center}
\includegraphics[scale=0.4]{sample.jpg}
\end{center}

\end{problem}

