Daily Disinfection

We're gonna scour every vat, every keg, every cook surface. We've gotta clean up every possible source of contamination, and only then we cook. Comprende?

• Jesse, Breaking Bad

To get $99.1\%$ 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 $n$ 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 $1$ 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.

Input data

The first line contains of the single integer $t$ ($1 \le t \le 10^5$) - the number of the test cases.

The first line of each of the $t$ test cases contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) - the number of the places on the shelf.

The second line contains a string $s$ of length $n$, where $s_i = 0$ if there is no book at $i$-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 $n$ over all test cases will not be greater than $2 \cdot 10^5$.

Output data

Output $t$ lines, each line containing a single integer - the minimal amount of power Jesse has to spend.

Example

stdin

3
2
01
5
00110
9
101010101

stdout

1
2
6

Explanation

In the first test case, Jesse can clean the first place, then move the book from the second place to the first (consuming $1$ power), and then clean the second place.