{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp style\u003d\"text-align: center;\"\u003e\u003cspan style\u003d\"font-size: large;\"\u003e\u003cstrong\u003e\u003cspan style\u003d\"font-size: medium;\"\u003e\u003ca href\u003d\"//spoj.com/problems/QWERTY04/\" target\u003d\"_blank\"\u003e\u003c/a\u003e\u003c/span\u003e\u003cbr\u003eTRIVIADOR\u003c/strong\u003e\u003c/span\u003e\u003c/p\u003e\r\n\u003cp\u003eTriviador is a war between two Kings. A king can attack an enemy region at each step. When a king attacks a region, he conquers all the enemy regions connected to it(not just the immediate ones). All the 8 regions around any region are connected to it. The kings get alternate chances to attack. King1 gets the chance to attack first. Assume both kings are intelligent and find who will conquer the whole territory at the end of the war. It can be proved that one of the Kings can win for sure if he is intelligent!\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003e\u0026nbsp;\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eInput Specification:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003eThe first line is an integer t, denotes the number of test cases. In each test case the first line consists of two integers denoting the number of rows and columns in the territory (each cell is a region). Then the description of each cell follows. Every region contains a character ‘X’ if it is owned by king1 or ‘O’ otherwise. \u003cbr\u003e \u003cbr\u003e \u003cbr\u003e \u003cstrong\u003eOutput Specification\u003c/strong\u003e:\u003cbr\u003e For each test case output the result in a single line ‘X’ if king1 wins or ‘O’ if king2 wins.\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003e\u0026nbsp;\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eInput Constraints:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eT\u0026lt;\u003d100\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003e1\u0026lt;\u003drows,columns\u0026lt;\u003d10\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003e\u0026nbsp;\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eSample input:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003e\u003cbr\u003e \u003c/strong\u003e3\u003c/p\u003e\r\n\u003cp\u003e3 3\u003c/p\u003e\r\n\u003cp\u003eXOX\u003c/p\u003e\r\n\u003cp\u003eXXX\u003c/p\u003e\r\n\u003cp\u003eXOX\u003c/p\u003e\r\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e3 5\u003c/p\u003e\r\n\u003cp\u003eXXXXX\u003c/p\u003e\r\n\u003cp\u003eXXXOO\u003c/p\u003e\r\n\u003cp\u003eXXXOO\u003c/p\u003e\r\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e4 4\u003c/p\u003e\r\n\u003cp\u003eXXXX\u003c/p\u003e\r\n\u003cp\u003eOOOO\u003c/p\u003e\r\n\u003cp\u003eXXXX\u003c/p\u003e\r\n\u003cp\u003eOOOO\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003e\u003cbr\u003eSample Output:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003eO\u003c/p\u003e\r\n\u003cp\u003eX\u003c/p\u003e\r\n\u003cp\u003eX\u003c/p\u003e\r\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eExplanation of testcase 1 and 2:\u003cbr\u003e\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eCase 1: \u003c/strong\u003eKing1 has two possibilities to attack. But after attacking any of them, he will lose surely when king2 attacks back.\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eCase 2: \u003c/strong\u003eKing1 can attack any of the four enemy positions. He conquers all the connected enemy positions. So this is a one step victory.\u003cstrong\u003e \u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cspan style\u003d\"font-size: small;\"\u003e\u003cbr\u003e\u003c/span\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cspan style\u003d\"font-size: small;\"\u003e \u003c/span\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cspan style\u003d\"font-size: small;\"\u003eTry the 1D version of this problem : \u003ca href\u003d\"//spoj.com/problems/QWERTY04/\" target\u003d\"_blank\"\u003e//spoj.com/problems/QWERTY04/\u003c/a\u003e\u003cbr\u003eTry the 3D version of this problem : \u003ca href\u003d\"//spoj.com/problems/CONQUER/\"\u003e//spoj.com/problems/CONQUER/\u003c/a\u003e\u003c/span\u003e\u003c/p\u003e\n\u003c/div\u003e"}}]}