{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAlpha Centauri-M (ACM) is a planet with marvelous scenes for visitors from the Earth. Luckily you win a ticket to participate in a space tour to Alpha Centauri-M.\u003c/p\u003e\u003cp\u003eThe map of the planet ACM is divided into a grid of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e rows and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e columns. The columns are indexed from 1 to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e (from left to right) and the rows are indexed from 1 to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e (from top to bottom). There are several cells on the map that are not safe for visitors to explore because of high mountains and volcanoes.\u003c/p\u003e\u003cp\u003eUpon arriving at ACM, the spaceship will land on any safe cell on the grid and passengers can visit the planet via a special system of space cars. From the landing cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e, \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e)\u003c/span\u003e on the map, a space car can go to either one of the four connected adjacent cells, namely \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e–1, \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e), (\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e + 1, \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e), (\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e, \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e–1), (\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e, \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e + 1)\u003c/span\u003e. Subsequently, the space car will continue moving the following fixed navigation pattern:\u003c/p\u003e\u003col\u003e \u003cli\u003e Turn right and go forward one cell \u003c/li\u003e\u003cli\u003e Turn left and go forward one cell \u003c/li\u003e\u003cli\u003e Go back to step 1. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eA space car can only visit safe cells, therefore it will stop if the next cell is not safe or is beyond the map boundaries. The following figure illustrates a map consisting of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e \u003d 6\u003c/span\u003e rows and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e \u003d 7\u003c/span\u003e columns. From the landing cell \u003cspan class\u003d\"tex-span\"\u003e(4, 3)\u003c/span\u003e, you may visit 16 cells (including the landing cell).\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/be0e5e631dff0ae444a48a1cdf7384d5?v\u003d1718500223\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\u003cp\u003eFor each landing cell on the map, you can determine the number of cells that you can visit (including the landing cell). Your task is to choose the landing cell from which you can visit the maximum number of cells on Alpha Centauri-M. \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 20. The following lines describe the datasets. \u003c/p\u003e\u003cp\u003eThe first line of a dataset contains 2 space-separated positive integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003eM\u003c/i\u003e, \u003ci\u003eN\u003c/i\u003e ≤ 1000)\u003c/span\u003e. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003eth line in the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e lines of the dataset contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e binary digits to represent the states of all cells in the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003eth row of the map (1: safe cell, 0: unsafe cell).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each dataset, write in one line the maximum number of cells that you can visit on Alpha Centauri-M (including the landing cell).\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e2\n3 3\n011\n111\n111\n6 7\n1101011\n0111111\n1111101\n1111111\n1111110\n0111111\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n20\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}