A. Brogramming Contesttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputOne 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$$$.InputThe 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$$$.OutputFor each testcase, output the minimum number of moves required.ExampleInput55001104111130015000003101Output2
1
1
0
3
NoteAn 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.