| Good Egg Galaxy — Koji Kondo, Super Mario Galaxy |
 |
Let $$$n$$$ be a positive integer. Mario has a binary string$$$^{\text{∗}}$$$ $$$s$$$ of length $$$n$$$. In one move, he can choose any position $$$i$$$ ($$$2 \leq i \leq n-1$$$) such that it's between two 1's, i.e., $$$s_{i-1} = s_{i+1} = \texttt{1}$$$, and then set $$$s_i$$$ to either 0 or 1.
Mario can perform this operation as many times as he wants (possibly zero). What's the minimum and maximum number of 1's that can be in the resulting string?
$$$^{\text{∗}}$$$A binary string is a string whose characters are either 0 or 1.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.
The first line of each test case contains an integer $$$n$$$ ($$$3 \leq n \leq 100$$$) — the length of the string.
The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of characters 0 or 1.
For each test case, output two integers — the minimum and maximum number of 1's in the resulting string after some number of moves.
431116011011710111019100101101
2 33 54 75 7
In the first test case, the minimum number of 1's that can be in the resulting string is $$$2$$$. This is done by transforming the string as follows: $$$$$$\mathtt{1}\underline{\mathtt{1}}\mathtt{1} \to \mathtt{101}.$$$$$$ The maximum number of 1's that can be in the resulting string is $$$3$$$, by doing nothing.
In the second test case, the minimum number of 1's that can be in the resulting string is $$$3$$$. This is done by transforming the string as follows: $$$$$$\mathtt{011}\underline{\mathtt{0}}\mathtt{11} \to \mathtt{01}\underline{\mathtt{1}}\mathtt{111} \to \mathtt{0101}\underline{\mathtt{1}}\mathtt{1} \to \mathtt{010101}.$$$$$$ The maximum number of 1's that can be in the resulting string is $$$5$$$. This is done by transforming the string as follows: $$$$$$\mathtt{011}\underline{\mathtt{0}}\mathtt{11} \to \mathtt{011111}.$$$$$$
