The Nights Watch
All submissions for this problem are available.###Read problems statements [Mandarin](http://www.codechef.com/download/translated/LTIME68/mandarin/WTCH.pdf) , [Bengali](http://www.codechef.com/download/translated/LTIME68/bengali/WTCH.pdf) , [Hindi](http://www.codechef.com/download/translated/LTIME68/hindi/WTCH.pdf) , [Russian](http://www.codechef.com/download/translated/LTIME68/russian/WTCH.pdf) and [Vietnamese](http://www.codechef.com/download/translated/LTIME68/vietnamese/WTCH.pdf) as well. There are $N$ watchtowers built in a row. Each watchtower can only accommodate one person. Some of them are already occupied by members of the Night's Watch. Since the members of the Night's Watch do not get along, no two consecutive towers can be occupied at any moment. Arya heard that the wildlings are planning an attack. She is not satisfied by the current security, so she plans to place more members of the Night's Watch in the empty towers. What is the maximum number of people she can place in the towers such that no two consecutive towers are occupied afterwards? Note that Arya may not remove anyone from already occupied towers. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains a single integer $N$. - The next line contains a single string $S$ with length $N$. For each valid $i$, the $i$-th character of this string is '1' if the $i$-th watchtower is initially occupied or '0' if it is empty. ### Output For each test case, print a single line containing one integer — the maximum number of people Arya can place in the towers. ### Constraints - $1 \le T \le 1,000$ - $1 \le N \le 10^6$ - $S$ contains only characters '0' and '1' - initially, no two consecutive towers are occupied - the sum of $N$ over all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (20 points):** initially, all towers are empty **Subtask #2 (80 points):** original constraints ### Example Input ``` 2 6 010001 11 00101010000 ``` ### Example Output ``` 1 3 ```
|Tags||implementation, ltime68, watcher|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.