A. Brogramming Contest
greedy; strings
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\).
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\).
For each testcase, output the minimum number of moves required.
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.