{"trustable":false,"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":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv id\u003d\"problem-body\"\u003e \n \u003cp\u003eIt\u0027s the year 21546 AD, and because of expanded populace (you wouldn\u0027t trust me on the off chance that I gave you the genuine numbers), land has gotten extravagant. On account of the absence of room, Heaven and Hell were worked in a similar region. The zone can be spoken to as a lattice of X × Y unit squares. A portion of the squares were caught by the Devil (and therefore have a place with Hell) and the rest is the Almighty\u0027s property. On each square, a room has been worked with straightforward glass dividers. Be that as it may, a portion of the superb rooms are now involved by Angels. For security purposes, rooms involved by Angels have solid obscure dividers. \u003c/p\u003e \n \u003cp\u003eAs of late numerous warriors were executed in a competition. Battling is not, at this point thought about barbarous, so all the contenders will merit spots in paradise. In any case, as a result of the space lack, every one of them will be unable to recieve a spot in paradise. The contenders despite everything hold resentment against one another so a warrior can\u0027t be set in a room from which he can perceive some other contender. A warrior can just find in the four cardinal ways (North, South, East and West). He can\u0027t glance corner to corner or in some other area. \u003c/p\u003e \n \u003cp\u003eFind the maximum number of fighters who can have a heavenly room.\u003c/p\u003e \n \u003ch3\u003eInput\u003c/h3\u003e \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 \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 \n \u003col\u003e \n \u003cli\u003e\"H\", if the room at location (i, j) is heavenly and vacant.\u003c/li\u003e \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 \n \u003cli\u003e\"D\", if the room at location (i, j) belongs to the Devil.\u003c/li\u003e \n \u003c/ol\u003e \n \u003cb\u003eOutput\u003c/b\u003e \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 \n \u003ch3\u003eExample\u003c/h3\u003e \n \u003cpre\u003e\n\u003cb\u003eInput:\u003c/b\u003e\n1\n4 7\nH H H H H H H\nH H H H H H H\nH H H H H H H\nH H H H H H H\n\n\u003cb\u003eOutput:\u003c/b\u003e\n4\n\u003c/pre\u003e \n \u003c/div\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}}]}