To get pure product, everything in the lab has to be thoroughly cleaned daily. Right now, Jesse is going to clean a shelf with books.
The shelf consists of places for books. There are some books placed on the shelf (possibly, none). If some place is empty, Jesse can clean it without any power consumption (he is really good at cleaning). He cannot clean any place with a book currently in it. If there is a book at some place, and the adjacent place is empty, Jesse can move the book to that adjacent place consuming power.
Jesse is a very busy person, and he does not want to spend too much power. For each test case, tell the minimal amount of power Jesse has to spend.
The first line contains of the single integer (1 \le t \le 10^5) — the number of the test cases.
The first line of each of the test cases contains a single integer (1 \le n \le 2 \cdot 10^5) — the number of the places on the shelf.
The second line contains a string of length , where s_i = 0 if there is no book at -th place, and s_1 = 1 otherwise.
It is guaranteed that in all provided test cases it is possible to clean the shelf.
The sum of over all test cases will not be greater than 2 \cdot 10^5.
Output lines, each line containing a single integer — the minimal amount of power Jesse has to spend.
Example
In the first test case, Jesse can do the following:
Clean the first place;
Move the book from the second place to the first (consuming power);
Clean the second place.