{"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\"\u003ePatrick Star found a world consist of N * N girds. Every gird is either black or write.\u003cbr\u003e\u003cbr\u003eIf one black gird $a$ is not \"reachable\" from another one black gird $b$, we said that the pair of $(a, b)$ is \"special pair\" ! What\u0027s more, Patrick Star regards the score of this pair as the Manhattan Distance between the two girds.\u003cbr\u003e\u003cbr\u003eFor every two girds, if there exist an path begin from one and end at another one, also this path consists only black girds and turns at most once, then the two girds are \"reachable\" from each other.\u003cbr\u003e\u003cbr\u003eFor better understanding of possible paths, every pair of gird (a, b) has only two possible paths while ignore the other limits, marked by \\#, and both paths include \"a\" and \"b\".\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003cbr\u003e\u003cbr\u003e\u003da#####\u003d\u003cbr\u003e\u003cbr\u003e\u003d#\u003d\u003d\u003d\u003d#\u003d\u003cbr\u003e\u003cbr\u003e\u003d#####b\u003d\u003cbr\u003e\u003cbr\u003e\u003cbr\u003eAnd see the text-picture below to get better understanding about \u0027reachable\u0027, we use \"1\" to stand for black gird and \"0\" to the white.\u003cbr\u003e\u003cbr\u003e11111111\u003cbr\u003e\u003cbr\u003e10110000\u003cbr\u003e\u003cbr\u003e10011110\u003cbr\u003e\u003cbr\u003e11111111\u003cbr\u003e\u003cbr\u003epair of [(2, 4), (4, 8)] : reachable. by path (2, 4) -\u0026gt; (4, 4) -\u0026gt; (4, 8).\u003cbr\u003e\u003cbr\u003epair of [(1, 5), (4, 8)] : not reachable, Manhattan Distance is |1 - 4| + |5 - 8| \u003d 6.\u003cbr\u003e\u003cbr\u003epair of [(1, 5), (4, 4)] : reachable. by path (1, 5) -\u0026gt; (1, 4) -\u0026gt; (4, 4).\u003cbr\u003e\u003cbr\u003epair of [(1, 5), (4, 3)] : not reachable, Manhattan Distance is |1 - 4| + |5 - 3| \u003d 5.\u003cbr\u003e...\u003cbr\u003e\u003cbr\u003e\u003cbr\u003eNow Patrick Star wants to know the max score among all special pairs.\u003cbr\u003e\u003cbr\u003eIf there is not any special pair , just output \"Opps!\".\u003cbr\u003e\u003cbr\u003eMoreover, assume that the maximum score described above is $D$ (if exist), Patrick Star wants know how many special pair has score of $D$. (unordered, that is to say $pair(a, b)$ is the same as $pair(b, a)$).\u003cbr\u003e\u003cbr\u003eIt is guaranteed that the two answers no more than 2147483647.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contain a integer $T$(no more than 10), the following is $T$ test case, for each test case:\u003cbr\u003e\u003cbr\u003eThe first line contains one integers $N(1 \\le N \\le 2000)$.\u003cbr\u003e\u003cbr\u003eThe following $N$ lines show an $N$ * $N$ girds. \u003cbr\u003e\u003cbr\u003eeach line contain a string of length $N$ consist of \"0\" or \"1\" which mean \"white\" or \"black\"\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case , output one line :\u003cbr\u003e\u003cbr\u003e1. If no exist special pair, just output \"Opps!\".\u003cbr\u003e\u003cbr\u003e2. Else output two integers separated by white space, the first one is the maximum score, and the second one is the number of special pairs reach the maximun score."}},{"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\u003e1\r\n4\r\n1011\r\n1001\r\n1001\r\n1111\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}