One day after waking up, your friend challenged you to a brogramming contest. In a brogramming contest, you are given a binary string$$$^{\text{∗}}$$$ $$$s$$$ of length $$$n$$$ and an initially empty binary string $$$t$$$. During a brogramming contest, you can make either of the following moves any number of times:

remove some suffix$$$^{\text{†}}$$$ from $$$s$$$ and place it at the end of $$$t$$$, or
remove some suffix from $$$t$$$ and place it at the end of $$$s$$$.

To win the brogramming contest, you must make the minimum number of moves required to make $$$s$$$ contain only the character $$$\texttt{0}$$$ and $$$t$$$ contain only the character $$$\texttt{1}$$$. Find the minimum number of moves required.

$$$^{\text{∗}}$$$A binary string is a string consisting of characters $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

$$$^{\text{†}}$$$A string $$$a$$$ is a suffix of a string $$$b$$$ if $$$a$$$ can be obtained from deletion of several (possibly, zero or all) elements from the beginning of $$$b$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case is an integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the length of the string $$$s$$$.

The second line of each test case contains the binary string $$$s$$$.

The sum of $$$n$$$ across all test cases does not exceed $$$1000$$$.

Output

For each testcase, output the minimum number of moves required.

Note

An optimal solution to the first test case is as follows:

$$$s = \texttt{00}\color{red}{\texttt{110}}$$$, $$$t =$$$ empty string.
$$$s = \texttt{00}$$$, $$$t = \texttt{11}\color{red}{\texttt{0}}$$$.
$$$s = \texttt{000}$$$, $$$t = \texttt{11}$$$.

It can be proven that there is no solution using less than $$$2$$$ moves.

In the second test case, you have to move the whole string from $$$s$$$ to $$$t$$$ in one move.

In the fourth test case, you don't have to do any moves.

Brogramming Contest

Examples