У Поликарпа есть прямоугольное поле размером \(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\) строк, каждая из строк должна содержать ответ на соответствующий набор входных данных: минимальное количество раз, которое Поликарпу нужно поставить Робота на верхнюю строку поля, чтобы собрать все конфеты.
Примечание
В первом наборе Поликарп может вообще не ставить Робота на поле, так что ответ 0
Во втором наборе Поликарпу потребуется два раза ставить робота на поле. Робот может собрать конфеты так: в первый раз Поликарп ставит Робота в клетку \((1, 1)\) соберет конфеты на позициях \((1, 1)\) и \((3, 3)\). Во второй раз Поликарп может снова поставить Робота в клетку \((1, 1)\) и тогда Робот переместится сначала в клетку \((2,2)\), затем в клетку \((3, 1)\) и соберет последнюю конфету.
В четвертом наборе можно показать, что за три прохода Робот не сможет собрать все конфеты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|