CF2064A Brogramming Contest

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.