题目描述

给定一个长度为 $n$ 的二进制字符串 $s$（每个字符要么是 0 要么是 1），你可以选择一个位置 $i$（$2\leq i\leq n-1$），当满足：$s_{i-1}=s_{i+1}=1$，你可以将 $s_i$ 修改为 $0$ 或 $1$。

你可以执行无限次上述操作，问字符串内 $1$ 的总数的最小值和最大值分别可能是多少？

输入格式

本题有多组数据

第一行输入一个整数 $t$，表示测试数据组数。每一组数据：

• 第一行输入一个整数 $n$ 表示字符串的长度。
• 第二行输入一个长度为 $n$ 的字符串 $s$。

输出格式

输出一共输出 $t$ 行，每行两个空格隔开的整数分别表示 $1$ 的数量的最小值和最大值。

4
3
111
6
011011
7
1011101
9
100101101

2 3
3 5
4 7
5 7

提示

第一个测试用例中，最终字符串中 $1$ 的最小数量是 $2$。操作过程是：

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

最大数量是 $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}. $$

最大数量是 $5$，操作过程是：

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

数据范围

对于 $100\%$ 的数据满足：$1 \leq t \leq 300$，$3 \leq n \leq 100$。字符串仅包含 0 和 1。

• 子任务 1（30 分）：保证字符串中任意两个 1 之间的距离至少为 3（即不存在子串 11 或 101）。
• 子任务 2（30 分）：保证输入字符串 $s$ 全由 1 组成。
• 子任务 3（40 分）：无特殊限制。