{"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\u003eIt\u0027s the year 21546 AD, and due to increased population (you wouldn\u0027t believe me if I gave you the actual numbers), land has become very expensive. Because of the lack of space, Heaven and Hell were built in the same area. The area can be represented as a grid of \u003cb\u003eX\u003c/b\u003e × \u003cb\u003eY\u003c/b\u003e unit squares. Some of the squares were captured by the Devil (and thus belong to Hell) and the rest is the Almighty\u0027s property. On each square, a room has been built with transparent glass walls. However, some of the heavenly rooms are already occupied by Angels. For security purposes, rooms occupied by Angels have concrete opaque walls.\u003c/p\u003e\r\n\r\n\u003cp\u003eRecently many fighters were killed in a tournament. Fighting is no longer considered cruel, so all the fighters will deserve spots in heaven. However, because of the space shortage, all of them may not be able to recieve a spot in heaven. The fighters still hold a grudge against each other so a fighter cannot be placed in a room from which he can see any other fighter. A fighter can only see in the four cardinal directions (North, South, East and West). He cannot look diagonally or in any other direction.\u003c/p\u003e\r\n\r\n\u003cp\u003eFind the maximum number of fighters who can have a heavenly room.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of the input contains an integer \u003cb\u003et\u003c/b\u003e, the number of test cases. \u003cb\u003et\u003c/b\u003e test cases follow.\u003c/p\u003e\r\n\r\n\u003cp\u003eThe first line of each test case consists of two integers \u003cb\u003eX\u003c/b\u003e \u0026lt;\u003d 300 and \u003cb\u003eY\u003c/b\u003e \u0026lt;\u003d 300, separated by a single space. Next, \u003cb\u003eX\u003c/b\u003e lines follow, each having \u003cb\u003eY\u003c/b\u003e letters separated by spaces. The jth letter on the i-th line is one of the following (quotes are for clarity, and do not appear in the input):\u003c/p\u003e\r\n\u003col\u003e\r\n\u003cli\u003e\"H\", if the room at location (i, j) is heavenly and vacant.\u003c/li\u003e\r\n\u003cli\u003e\"A\", if the room at location (i, j) is heavenly and is already occupied by an angel. Note that these rooms are not transparent.\u003c/li\u003e\r\n\u003cli\u003e\"D\", if the room at location (i, j) belongs to the Devil.\u003c/li\u003e\r\n\u003c/ol\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eA single line for each test case containing an integer denoting the maximum number of fighters that can fit in heaven.\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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 7\r\nH H H H H H H\r\nH H H H H H H\r\nH H H H H H H\r\nH H H H H H H\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\u003c/div\u003e"}}]}