ROCK - Sweet and Sour Rock

A manufacturer of sweets has started production of a new type of sweet called rock. Rock comes in sticks composed of one-centimetre-long segments, some of which are sweet, and the rest are sour. Before sale, the rock is broken up into smaller pieces by splitting it at the connections of some segments.

Today's children are very particular about what they eat, and they will only buy a piece of rock if it contains more sweet segments than sour ones. Try to determine the total length of rock which can be sold after breaking up the rock in the best possible way.

Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case, the first line of input contains one integer N - the length of the stick in centimetres (1<=N<=200). The next line is a sequence of N characters '0' or '1', describing the segments of the stick from the left end to the right end ('0' denotes a sour segment, '1' - a sweet one).

Output

For each test case output a line with a single integer: the total length of rock that can be sold after breaking up the rock in the best possible way.

Example

Sample input:
2
15
100110001010001
16
0010111101100000

Sample output:
9
13

Added by:adrian
Date:2004-08-03
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:based on a problem from the VII Polish Collegiate Team Programming Contest (AMPPZ), 2002

hide comments
2014-02-06 06:31:21 Cloud Strife
Nice question!
2013-11-29 14:01:11 harsh
nyc problem..
2013-07-21 18:59:28 Dragan MarkoviƦ
I don't know if it's allowed but here's a little hint : When you have problem like this always think of regular expressions.
2013-06-15 09:31:16 Prajit Patil
0000110100100
7
try this case
2013-04-24 10:05:40 another_clone
what should be the output for wrong cases ?
1)length >200
2)length=200 but stringlength>200
3)string contains non binary chararcters

my solution works for all strings from length 1 to 200, with ease. max time taken is 0.02. however i keep getting wrong answer.


2012-09-18 16:27:47 Prashant Mishra
can someone tell some test cases... getting WA?
2012-08-26 01:10:50 KEVALSAHU
simple problem guys :)

Last edit: 2012-08-26 01:15:23
2011-01-28 14:09:12 Caesum
I think the pieces are 10011,101,1
and for the second 0010111101100
2011-01-27 20:52:33 ANSHU ANAND
i guess the output for the first test case in the example is wrong , it should be 5 its no way 9
2011-01-23 09:33:19 Gokul Sundar
i think the question is very unclear. can anyone elaborate on the test cases or what exactly is the "best possible way".
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.