{"trustable":false,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"PLAIN","content":"昨晚,小二日月做了一个可怕的噩梦。他梦到他和他的女朋友被分开困在了一个迷宫里。更糟糕的是,迷宫里有两只幽灵,它们会杀死它们遇到的人。现在小二日月想知道他能否在幽灵找到他们之前找到他的女朋友。\n小二日月和他的女朋友可以向四个方向移动。每一秒,小二日月可以移动三步,他的女朋友可以移动一步。幽灵非常邪恶,每一秒它们会分裂成多个部分并占领2步以内的所有格子,直到它们占领了整个迷宫。每一秒幽灵先分裂,然后小二日月和他的女朋友才开始移动。一旦小二日月或者他的女朋友踏入了被幽灵占领的格子,他们会立刻死亡。\n注意:分裂出的新幽灵和原幽灵一样可以再次分裂。"}},{"title":"Input","value":{"format":"PLAIN","content":"第一行一个整数T,表示测试数据组数。\n每一组测试数据第一行两个整数n和m,表示迷宫的大小(1\u003cn,m\u003c800)。\n之后n行表示迷宫,每行有m个字符。\n\u0027.\u0027:空地\n\u0027X\u0027:墙,只有人不能穿过\n\u0027M\u0027:小二日月\n\u0027G\u0027:女朋友\n\u0027Z\u0027:幽灵\n保证只有一个M,一个G,两个Z"}},{"title":"Output","value":{"format":"PLAIN","content":"对于每组数据输出一行一个整数,如果他们能成功小于,输出他们最快能相遇的时间,否则输出-1"}},{"title":"Sample Input","value":{"format":"PLAIN","content":"3\n5 6\nXXXXXX\nXZ..ZX\nXXXXXX\nM.G...\n......\n5 6\nXXXXXX\nXZZ..X\nXXXXXX\nM.....\n..G...\n\n10 10\n..........\n..X.......\n..M.X...X.\nX.........\n.X..X.X.X.\n.........X\n..XX....X.\nX....G...X\n...ZX.X...\n...Z..X..X"}},{"title":"Sample Output","value":{"format":"PLAIN","content":"1\n1\n-1"}}]}