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

У Поликарпа есть прямоугольное поле размером $$$n \times m$$$ клеток (размер поля $$$n \cdot m$$$ не превышает $$$10^6$$$ клеток, $$$m \ge 2$$$), в каждой клетке которого может быть конфета. Поле состоит из $$$n$$$ строк и $$$m$$$ столбцов.

Обозначим клетку с координатами $$$x$$$ по вертикали и $$$y$$$ по горизонтали за $$$(x, y)$$$. Тогда левая верхняя клетка будет обозначаться как $$$(1, 1)$$$, а правая нижняя — как $$$(n, m)$$$.

Если в клетке поля есть конфета, то клетка поля помечена символом «1», иначе — символом «0».

Поликарп сконструировал Робота, который может собирать конфеты. Робот может переместиться из клетки $$$(x, y)$$$ либо в клетку $$$(x+1, y+1)$$$, либо в клетку $$$(x+1, y-1)$$$. Если Робот находится в клетке, в которой есть конфета, он её забирает.

Пока на поле есть хотя бы одна конфета, выполняется следующий алгоритм:

  • Поликарп ставит Робота в произвольную клетку первой (верхней) строки поля. Он сам выбирает в какую клетку поставить Робота. Робота можно ставить в одну и ту же клетку несколько раз.
  • Робот перемещается по полю и собирает конфеты. Поликарп управляет Роботом. Когда Робот покидает поле, Поликарп подбирает его.
  • Если на поле есть хотя бы одна конфета, Поликарп повторяет алгоритм.

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

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

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

Перед каждым набором в тесте записана пустая строка. Далее идёт строка, которая содержит целые числа $$$n$$$ и $$$m$$$ ($$$2 \le m$$$, $$$2 \le n \cdot m \le 10^6$$$) — размеры поля. Затем следуют $$$n$$$ строк, $$$i$$$-я из которых описывает $$$i$$$-ю строку поля. Каждая из них представляет собой строку размера $$$m$$$ символов: cимвол «1» соответствует клетке с конфетой, символ «0» — пустой клетке.

Гарантируется, что сумма значений $$$n \cdot m$$$ по всем наборам входных данных в тесте не превосходит $$$10^6$$$.

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

Выведите $$$t$$$ строк, каждая из строк должна содержать ответ на соответствующий набор входных данных: минимальное количество раз, которое Поликарпу нужно поставить Робота на верхнюю строку поля, чтобы собрать все конфеты.

Пример
Входные данные
4

2 2
00
00

3 3
100
000
101

4 5
01000
00001
00010
10000

3 3
111
111
111
Выходные данные
0
2
2
4
Примечание

В первом наборе Поликарп может вообще не ставить Робота на поле, так что ответ 0

Во втором наборе Поликарпу потребуется два раза ставить робота на поле. Робот может собрать конфеты так: в первый раз Поликарп ставит Робота в клетку $$$(1, 1)$$$ соберет конфеты на позициях $$$(1, 1)$$$ и $$$(3, 3)$$$. Во второй раз Поликарп может снова поставить Робота в клетку $$$(1, 1)$$$ и тогда Робот переместится сначала в клетку $$$(2,2)$$$, затем в клетку $$$(3, 1)$$$ и соберет последнюю конфету.

В четвертом наборе можно показать, что за три прохода Робот не сможет собрать все конфеты.