题目描述

Good Egg Galaxy — Koji Kondo, Super Mario Galaxy

设 $n$ 为一个正整数。Mario 有一个长度为 $n$ 的二进制串 $s$。

每一步操作中，他可以选择任意一个位置 $i$（$2 \leq i \leq n-1$），该位置需要同时满足它的左右相邻位置都是 $1$，即 $s_{i-1} = s_{i+1} = 1$，然后将 $s_i$ 改为 $0$ 或 $1$。

Mario 可以进行任意次数（也可以一次都不做）上述操作。请你求出最终字符串中 $1$ 的最小个数和最大个数分别是多少？

注：二进制串是指所有字符都是 $0$ 或 $1$ 的字符串。

输入格式

每组测试数据包含多个测试用例。第一行输入一个整数 $t$（$1 \leq t \leq 500$），表示测试用例数量。

每个测试用例的第一行输入一个整数 $n$（$3 \leq n \leq 100$），表示字符串的长度。

每个测试用例的第二行输入一个长度为 $n$ 的二进制串 $s$。

输出格式

对于每组测试用例，输出两个整数，表示经过任意次操作后，最终字符串中 $1$ 的最小和最大个数。

说明/提示

在第一个测试用例中，最终字符串中 $1$ 的最小个数为 $2$，可以按如下方式转换：

$$\mathtt{1}\underline{\mathtt{1}}\mathtt{1} \to \mathtt{101}$$

最大个数为 $3$，即不进行任何操作。

在第二个测试用例中，最小个数为 $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}$$

最大个数为 $5$，转换过程如下：

$$\mathtt{011}\underline{\mathtt{0}}\mathtt{11} \to \mathtt{011111}$$

由 ChatGPT 5 翻译

样例

4
3
111
6
011011
7
1011101
9
100101101

2 3
3 5
4 7
5 7