该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

相邻夹击（One）

题目描述

乐柠兔有一个长度为 $n$ 的二进制字符串 $s$，字符串中的每个字符都是 0 或 1。

乐柠兔可以进行任意多次操作，也可以一次都不操作。每次操作可以选择一个位置 $i$，满足 $2\le i\le n-1$，并且位置 $i$ 左右两侧的字符都是 1，也就是

然后乐柠兔可以把 $s_i$ 改成 0 或 1。

请你求出：经过任意多次操作后，字符串中 1 的数量最少可以是多少，最多可以是多少。

你需要独立处理 $T$ 组数据。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

对于每组数据：

第一行包含一个整数 $n$。

第二行包含一个长度为 $n$ 的二进制字符串 $s$。

输出格式

对于每组数据，输出一行两个整数，分别表示最终字符串中 1 的数量最小值和最大值。

样例

样例输入 #1

4
3
111
6
011011
7
1011101
9
100101101

样例输出 #1

2 3
3 5
4 7
5 7

样例解析

对于第一组数据，字符串为 111。可以选择中间位置，把它改成 0，得到 101，此时 1 的数量为 $2$；如果不操作，1 的数量为 $3$。

对于第二组数据，字符串为 011011。最多时可以把中间的单个 0 改成 1，得到 011111，共有 $5$ 个 1。最少时可以得到形如 010101 的字符串，共有 $3$ 个 1。

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le T\le 500$，$3\le n\le 100$，$s$ 只包含字符 0 和 1。

• 特殊性质 A：保证每组数据的字符串中不存在连续两个 0。
• 特殊性质 B：保证每组数据的字符串全为 1 或全为 0。
• 特殊性质 C：保证每组数据的字符串为 0 和 1 交替出现。