{"trustable":true,"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":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e Little Ming\u0027s mother gave birth to three children. The eldest is called Da Ming, the second is called Er Ming, and the third... well, the third is naturally called Xiao Ming.\u003cbr\u003e One day, Little Ming\u0027s mother took the three brothers to the park to play. There were many trees in the park, providing plenty of places to hide, so they decided to play hide and seek. After a few rounds of rock-paper-scissors, it was decided that in the first round, Xiao Ming would be the seeker. The rules of the game were simple:\u003cbr\u003e If Xiao Ming could find the other two within the specified time, he would win and the two found brothers would play rock-paper-scissors to decide who would seek in the next round. If he only found one of them within the specified time, the one not found would win, and the one found would seek in the next round. If he didn\u0027t find anyone within the specified time, then Xiao Ming would lose and still be the seeker in the next round. Now Xiao Ming wants to know if he can find all the people within the specified time, and he wants you to help him calculate.\u003cbr\u003e For simplicity, let\u0027s consider the park as an n by m matrix, where \u0027S\u0027 represents Xiao Ming, \u0027D\u0027 represents Da Ming, \u0027E\u0027 represents Er Ming, \u0027X\u0027 represents an obstacle, and \u0027.\u0027 represents a pathway. Here, we define \"found\" as being able to directly see the other person, meaning that two people are in the same row or column, and there are no obstacles or other people in between. Also, assume that after Da Ming and Er Ming hide, they will not change their positions, and Xiao Ming can move to one of the four adjacent positions from his current position in each unit of time, without leaving the park.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the test data is a positive integer T, indicating the number of test cases.\u003cbr\u003eFor each test case, the first line consists of three positive integers n, m, and t, representing the number of rows, columns, and the specified time, followed by n lines, each containing m of the aforementioned characters. It is guaranteed that there is exactly one \u0027S\u0027, one \u0027E\u0027, and one \u0027D\u0027.\u003cbr\u003e\u003cbr\u003e\u003cb\u003e[Technical Specification]\u003c/b\u003e\u003cbr\u003eT \u0026lt; 200\u003cbr\u003e3 \u0026lt;\u003d n, m \u0026lt;\u003d 100\u003cbr\u003e0 \u0026lt;\u003d t \u0026lt;\u003d 100\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, first output a line \"Case c:\" (where c represents the current case number, starting from 1).\u003cbr\u003eThen, output a line with the minimum time needed if Xiao Ming can find all the people within the specified time, or -1 if not.\u003cbr\u003e"}},{"title":"Sample","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\u003e3\r\n5 6 3\r\nXXD...\r\n....E.\r\n....X.\r\n....S.\r\n......\r\n5 6 3\r\nXDX...\r\n....E.\r\n......\r\n....S.\r\n......\r\n5 6 8\r\nXXDX..\r\n.XEX..\r\n......\r\n....S.\r\n......\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1:\r\n-1\r\nCase 2:\r\n3\r\nCase 3:\r\n-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}