← 返回题目列表

Codeforces · 2207/A

A. 一减一

中文机器翻译题面 查看原题
Good Egg Galaxy — Koji Kondo,《超级马里奥银河》

令 $$$n$$$ 为正整数。 Mario 有一个长度为 $$$n$$$ 的二进制字符串$$$^{\text{∗}}$$$ $$$s$$$。在一步中,他可以选择任意位置 $$$i$$$ ($$$2 \leq i \leq n-1$$$) ,使其位于两个位置之间 1's,即 $$$s_{i-1} = s_{i+1} = \texttt{1}$$$,然后将 $$$s_i$$$ 设置为 0 or 1.

Mario 可以根据需要多次执行此操作(可能为零)。最小和最大数量是多少 1可以出现在结果字符串中吗?

$$$^{\text{*}}$$$二进制字符串是一个字符串,其字符是 0 or 1.

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

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

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符组成 0 or 1.

输出

对于每个测试用例,输出两个整数——最小和最大数量 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}.$$ 的最大数量 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}.$$