CF2207A.1-1

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.

好蛋星系 — 小岛良平，《超级马力欧银河》

设 $n$ 为一个正整数。马力欧有一个长度为 $n$ 的二进制字符串$^{\text{∗}}$ $s$。在一次操作中，他可以选择任意位置 $i$（其中 $2 \leq i \leq n-1$），满足该位置位于两个 1 之间，即 $s_{i-1} = s_{i+1} = \texttt{1}$，然后将 $s_i$ 设置为 0 或 1。

马力欧可以执行该操作任意多次（包括零次）。最终字符串中 1 的个数的最小值和最大值分别是多少？

$^{\text{∗}}$二进制字符串是指仅由字符 0 或 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.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 100$）—— 字符串的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 0 或 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.

对于每个测试用例，输出两个整数——经过若干次操作后，所得字符串中 1 的个数的最小值和最大值。

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}.$$

在第一个测试用例中，结果字符串中可能的最少 1 的个数为 $2$。通过如下变换实现：$$\mathtt{1}\underline{\mathtt{1}}\mathtt{1} \to \mathtt{101}.$$ 结果字符串中可能的最多 1 的个数为 $3$，此时不进行任何操作。

在第二个测试用例中，结果字符串中可能的最少 1 的个数为 $3$。通过如下变换实现：$$\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}.$$ 结果字符串中可能的最多 1 的个数为 $5$。通过如下变换实现：$$\mathtt{011}\underline{\mathtt{0}}\mathtt{11} \to \mathtt{011111}.$$