{"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\u003eA honeycomb is a mass wax cells built by honey bees, which can be described as a regular tiling of the Euclidean plane, in which three hexagons meet at each internal vertex. The internal angle of a hexagon is $$$120$$$ degrees, so three hexagons at a point make a full $$$360$$$ degrees. The following figure shows a complete honeycomb with $$$3$$$ rows and $$$4$$$ columns.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/f6f960b1d3d570555f01f75a4e8e1f98?v\u003d1715606620\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eHere we guarantee that the first cell in the second column always locates in the bottom right side of the first cell in the first column, as shown above. A general honeycomb may, on the basis of a complete honeycomb, lose some walls between adjacent cells, but the honeycomb is still in a closed form. A possible case looks like the figure below.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/b4adf4a68a96ee456978d224a0a4ff4c?v\u003d1715606620\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eHamilton is a brave bee living in a general honeycomb. Now he wants to move from a starting point to a specified destination. The image below gives a feasible path in a $$$3 \\times 4$$$ honeycomb from the $$$1$$$-st cell in the $$$2$$$-nd column to the $$$1$$$-st cell in the $$$4$$$-th column.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/46ec35a0d156f88b719bc16b33b8a8d7?v\u003d1715606620\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003ePlease help him find the minimum number of cells that a feasible path has to pass through (including the starting point and the destination) from the specified starting point to the destination.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input contains several test cases, and the first line contains a positive integer $$$T$$$ indicating the number of test cases which is up to $$$10^4$$$.\u003c/p\u003e\u003cp\u003eFor each test case, the first line contains two integers $$$r$$$ and $$$c$$$ indicating the number of rows and the number of columns of the honeycomb, where $$$2 \\leq r, c \\leq 10^3$$$.\u003c/p\u003e\u003cp\u003eThe following $$$(4 r + 3)$$$ lines describe the whole given honeycomb, where each line contains at most $$$(6 c + 3)$$$ characters. Odd lines contain grid vertices represented as plus signs (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003e+\u003c/span\u003e\") and zero or more horizontal edges, while even lines contain two or more diagonal edges. Specifically, a cell is described as $$$6$$$ vertices and at most $$$6$$$ edges. Its upper boundary or lower boundary is represented as three consecutive minus signs (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003e-\u003c/span\u003e\"). Each one of its diagonal edges, if exists, is a single forward slash (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003e/\u003c/span\u003e\") or a single backslash (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003e\\\u003c/span\u003e\") character. All edge characters will be placed exactly between the corresponding vertices. At the center of the starting cell (resp. the destination), a capital \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eS\u003c/span\u003e\" (resp. a capital \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eT\u003c/span\u003e\") as a special character is used to indicate the special cell. All other characters will be space characters. Note that if any input line could contain trailing whitespace, that whitespace will be omitted.\u003c/p\u003e\u003cp\u003eWe guarantee that all outermost wall exist so that the given honeycomb is closed, and exactly one \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eS\u003c/span\u003e\" and one \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eT\u003c/span\u003e\" appear in the given honeycomb. Besides, the sum of $$$r \\cdot c$$$ in all test cases is up to $$$2 \\times 10^6$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output a line containing the minimum number of cells that Hamilton has to visit moving from the starting cell (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003eS\u003c/span\u003e\") to the destination (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003eT\u003c/span\u003e\"), including the starting cell and the destination. If no feasible path exists, output \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e instead.\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\u003e1\n3 4\n +---+ +---+\n / \\ / \\\n+ +---+ +---+\n \\ \\ / \\\n + + S +---+ T +\n / \\ / /\n+ +---+ + +\n \\ \\ / \\\n +---+ +---+ +\n / /\n+ +---+ + +\n \\ / \\\n +---+ +---+ +\n \\ / \\ /\n +---+ +---+\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}