B"Polycarp has a rectangular field of n x m cells (the size of the n cdot m field does not exceed 10^6 cells, m ge 2 ), in each cell of which there can be candy. There are n rows and m columns in the field. Let's denote a cell with coordinates x vertically and y horizontally by (x, y) . Then the top-left cell will be denoted as (1, 1) , and the bottom-right cell will be denoted as (n, m) . If there is candy in the cell, then the cell is marked with the symbol '1', otherwise -- with the symbol '0'. Polycarp made a Robot that can collect candy. The Robot can move from (x, y) either to (x+1, y+1) , or to (x+1, y-1) . If the Robot is in a cell that contains candy, it takes it. While there is at least one candy on the field, the following procedure is executed: Find the minimum number of times Polycarp needs to put the Robot on the topmost row of the field in order to collect all the candies. It is guaranteed that Polycarp can always collect all the candies. The first line of input data contains an integer t ( 1 <= t <= 10^4 ) -- the number of input data sets in the test. Before each input data, there is a blank line in the test. Next is a line that contains integers n and m ( 2 <= m , 2 <= n cdot m <= 10^6 ) -- field sizes. This is followed by n lines, i -th of which describes the i -th line of the field. Each of them is a string of size m characters: the symbol '1' corresponds to a cell with candy, the symbol '0' -- an empty cell. It is guaranteed that the sum of n cdot m values for all input data sets in the test does not exceed 10^6 . Print t lines, each line should contain the answer to the corresponding set of input data: the minimum number of times Polycarpus needs to put the Robot on the topmost row of the field in order to collect all the candies. In the first set Polycarp may not put the"...