{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePaper-cutting is one of the oldest and most popular folk arts in China. It can be geographically divided into a southern and a northern style. The southern style, represented by works from Yangzhou in Jiangsu Province and Yueqing in Zhejiang Province, features ingenious and beautiful designs, exquisite carving and interesting shapes. The northern style, mainly from Yuxian and Fengning in Hebei Province and best represented by works from northern Shaanxi, features exaggerated shapes, vigorousness, vivid depictions, and diverse patterns.\u003c/p\u003e\n\u003cp\u003eThere are basic cut-outs, consisting of a single image, and symmetrical designs, that are usually created by some folding over a proportioned crease, and then cutting a shape, so that when unfolded, it forms a symmetrical design. Chinese paper cuttings are usually symmetrical. The paper cutouts are usually in an even number series of $2$, $4$, $24$, etc.\u003c/p\u003e\n\u003cp\u003eYou are given a piece of paper in the shape of a matrix of size $n \\times m$ and it is partitioned into $n \\times m$ blocks of size $1 \\times 1$. The piece of paper can be folded in the following way:\u003c/p\u003e\n\u003col\u003e\n\u003cli\u003eYou choose a vertical line between two of its columns or a horizontal line between two of its rows. This line splits the paper into two sides.\u003c/li\u003e\n\u003cli\u003eYou use the line as the folding axis and fold the smaller side of the paper onto the larger one going over the axis. If both sides of the paper are of equal size, you may fold from either side.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp\u003eYou would like to make a paper-cutting masterpiece from this paper. At first, you fold the paper using the method above several times (including zero times). Then you use scissors to cut the paper and each time you can cut out a connected component from the paper and throw it away. Note that two $1 \\times 1$ blocks are connected if they share an edge.\u003c/p\u003e\n\u003cp\u003eGiven the final look of the paper -- a matrix of size $n \\times m$ containing $0$s and $1$s, you would like to know the minimum number of cuts needed when using the scissors.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\u003cp\u003eThe first line contains two integers $n$ and $m$ ($1 \\le n \\times m \\le 10^6$) -- the size of the paper.\u003c/p\u003e\n\u003cp\u003eEach of the next $n$ lines contains a binary string of length $m$, where \u00270\u0027 means the $1 \\times 1$ block is cut out and \u00271\u0027 means the $1 \\times 1$ block remains on the final paper-cutting.\u003c/p\u003e\n\u003cp\u003eIt is guaranteed that the sum of $n \\times m$ over all test cases does not exceed $10^6$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing one integer, indicating the minimum number of cuts needed.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2 5\n11001\n11001\n5 7\n1001100\n0110011\n0101101\n0010010\n1000000\n3 2\n11\n11\n11\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n4\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eFor the first sample test case, you can fold in the following way and cut the only $0$ out: $\\begin{array}{ccc|cc} 1\u0026amp;1\u0026amp;0\u0026amp;0\u0026amp;1\\\\1\u0026amp;1\u0026amp;0\u0026amp;0\u0026amp;1\\end{array} \\to \\begin{array}{ccc} 1\u0026amp;1\u0026amp;0\\\\ \\hline 1\u0026amp;1\u0026amp;0\\end{array} \\to \\begin{array}{ccc} 1\u0026amp;1\u0026amp;0\\end{array}$\u003c/p\u003e\n\u003cp\u003eFor the second sample test case, you can fold in the following way and cut the $4$ connected components of $0$s out: $\\begin{array}{cccc|ccc} 1\u0026amp;0\u0026amp;0\u0026amp;1\u0026amp;1\u0026amp;0\u0026amp;0\\\\0\u0026amp;1\u0026amp;1\u0026amp;0\u0026amp;0\u0026amp;1\u0026amp;1\\\\0\u0026amp;1\u0026amp;0\u0026amp;1\u0026amp;1\u0026amp;0\u0026amp;1\\\\0\u0026amp;0\u0026amp;1\u0026amp;0\u0026amp;0\u0026amp;1\u0026amp;0\\\\1\u0026amp;0\u0026amp;0\u0026amp;0\u0026amp;0\u0026amp;0\u0026amp;0\\end{array} \\to\\begin{array}{cccc} 1\u0026amp;0\u0026amp;0\u0026amp;1\\\\0\u0026amp;1\u0026amp;1\u0026amp;0\\\\0\u0026amp;1\u0026amp;0\u0026amp;1\\\\0\u0026amp;0\u0026amp;1\u0026amp;0\\\\1\u0026amp;0\u0026amp;0\u0026amp;0\\end{array}$\u003c/p\u003e\n"}}]}