{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"yass_top_edge_dummy\" style\u003d\"width: 1px; height: 1px; padding: 0px; margin: -9px 0px 0px; border-width: 0px; display: block;\"\u003e\r\n\t\u0026nbsp;\u003c/div\u003e\r\n\u003cdiv id\u003d\"yass_top_edge\" style\u003d\"background-image: url(\u0026quot;chrome://yass/content/edgebgtop.png\u0026quot;); background-attachment: scroll; background-position: center bottom; padding: 0px; margin: 0px 0px 8px -8px; border-width: 0px; height: 0px; display: block; width: 1px;\"\u003e\r\n\t\u0026nbsp;\u003c/div\u003e\r\n\u003cdiv class\u003d\"Section1\"\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"font-size:18px;\"\u003e\u003cspan data-scayt_word\u003d\"Zipu\" data-scaytid\u003d\"1\"\u003eZipu\u003c/span\u003e owns a very long field. He plans to grow different types of crops in the upcoming growing season. The area, however, is full of crows and \u003cspan data-scayt_word\u003d\"Zipu\" data-scaytid\u003d\"2\"\u003eZipu\u003c/span\u003e fears that they might feed on most of the crops. For this reason, he has decided to place some scarecrows at different locations of the field.\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"font-size:18px;\"\u003eThe field can be modeled as a \u003cb\u003e1 x N\u003c/b\u003e grid. Some parts of the field are infertile and that means you cannot grow any crops on them. A scarecrow, when placed on a spot, covers the cell to its immediate left and right along with the cell it is on.\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"font-size:18px;\"\u003eGiven the description of the field, what is the minimum number of scarecrows that needs to be placed so that all the useful section of the field is covered? Useful section refers to cells where crops can be grown.\u003c/span\u003e\u003c/p\u003e\r\n\t\u003ch1\u003e\r\n\t\tInput\u003c/h1\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\tInput starts with an integer \u003cb\u003eT (\u0026le; 100)\u003c/b\u003e, denoting the number of test cases.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\tEach case starts with a line containing an integer \u003cb\u003eN (0 \u0026lt; N \u0026lt; 100)\u003c/b\u003e. The next line contains \u003cb\u003eN\u003c/b\u003e characters that describe the field. A dot \u003cb\u003e(.)\u003c/b\u003e indicates a crop-growing spot and a hash \u003cb\u003e(#)\u003c/b\u003e indicates an infertile region.\u003c/p\u003e\r\n\t\u003ch1\u003e\r\n\t\tOutput\u003c/h1\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\tFor each case, output the case number first followed by the number of scarecrows that need to be placed.\u003c/p\u003e\r\n\t\u003cbr /\u003e\r\n\t\u003cdiv align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\r\ntext-align:center\"\u003e\r\n\t\t\u003chr align\u003d\"center\" size\u003d\"2\" width\u003d\"100%\" /\u003e\r\n\t\u003c/div\u003e\r\n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n\u003cspan style\u003d\"font-size:12.0pt;font-family:Courier\"\u003e3\u003c/span\u003e\u003c/pre\u003e\r\n\u003cpre\u003e\r\n\u003cspan style\u003d\"font-size:12.0pt;font-family:Courier\"\u003e3\u003c/span\u003e\u003c/pre\u003e\r\n\u003cpre\u003e\r\n\u003cspan style\u003d\"font-size:12.0pt;font-family:Courier\"\u003e.#.\u003c/span\u003e\u003c/pre\u003e\r\n\u003cpre\u003e\r\n\u003cspan style\u003d\"font-size:12.0pt;font-family:Courier\"\u003e11\u003c/span\u003e\u003c/pre\u003e\r\n\u003cpre\u003e\r\n\u003cspan style\u003d\"font-size:12.0pt;font-family:Courier\"\u003e...##....##\u003c/span\u003e\u003c/pre\u003e\r\n\u003cpre\u003e\r\n\u003cspan style\u003d\"font-size:12.0pt;font-family:Courier\"\u003e2\u003c/span\u003e\u003c/pre\u003e\r\n\u003cpre\u003e\r\n\u003cspan style\u003d\"font-size:12.0pt;font-family:Courier\"\u003e##\u003c/span\u003e\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\n\u003cspan style\u003d\"font-size:18px;\"\u003e\u003cspan style\u003d\"font-family: Courier;\"\u003eCase 1: 1\u003c/span\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\u003cpre\u003e\r\n\u003cspan style\u003d\"font-size:18px;\"\u003e\u003cspan style\u003d\"font-family: Courier;\"\u003eCase 2: 3\u003c/span\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\u003cpre\u003e\r\n\u003cspan style\u003d\"font-size:18px;\"\u003e\u003cspan style\u003d\"font-family: Courier;\"\u003eCase 3: 0\u003c/span\u003e\u003c/span\u003e\u003c/pre\u003e"}}]}