{"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\u003e\r\n\tA manufacturer of sweets has started production of a new type of \r\n\tsweet called \u003cem\u003erock\u003c/em\u003e. Rock comes in sticks composed of \r\n\tone-centimetre-long segments, some of which are sweet, and the rest are sour. \r\n\tBefore sale, the rock is broken up into smaller pieces by splitting it at the \r\n\tconnections of some segments.\r\n\u003c/p\u003e\r\n\u003cp\u003eToday\u0027s children are very particular about what they eat, and they will only buy \r\n\ta piece of rock if it contains more sweet segments than sour ones. Try to \r\n\tdetermine the total length of rock which can be sold after breaking \r\n\tup the rock in the best possible way.\r\n\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003e\r\n\tThe input begins with the integer t, the number of test cases. Then t test \r\n\tcases follow.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\n\tFor each test case, the first line of input contains one integer N - the length \r\n\tof the stick in centimetres (1\u0026lt;\u003dN\u0026lt;\u003d200). The next line is a sequence of N \r\n\tcharacters \u00270\u0027 or \u00271\u0027, describing the segments of the stick from the left end \r\n\tto the right end (\u00270\u0027 denotes a sour segment, \u00271\u0027 - a sweet one).\r\n\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003e\r\n\tFor each test case output a line with a single integer: the total length of \r\n\trock that can be sold after breaking up the rock in the best possible way.\r\n\u003c/p\u003e\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\u003e2\r\n15\r\n100110001010001\r\n16\r\n0010111101100000\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\r\n13\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\n\u003c/div\u003e"}}]}