A. 1-1
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Good Egg Galaxy — Koji Kondo, Super Mario Galaxy

Пусть $$$n$$$ — положительное целое число. У Марио есть двоичная строка$$$^{\text{∗}}$$$ $$$s$$$ длиной $$$n$$$. За один ход он может выбрать любую позицию $$$i$$$ ($$$2 \leq i \leq n-1$$$), которая находится между двумя 1, т.е. $$$s_{i-1} = s_{i+1} = \texttt{1}$$$, и затем установить значение $$$s_i$$$ в либо 0, либо 1.

Марио может выполнять эту операцию столько раз, сколько захочет (возможно, ноль). Каково минимальное и максимальное количество 1, которые могут быть в результирующей строке?

$$$^{\text{∗}}$$$Двоичная строка — это строка, символы которой являются либо 0, либо 1.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$3 \leq n \leq 100$$$) — длина строки.

Вторая строка каждого набора содержит строку $$$s$$$ длиной $$$n$$$, состоящую из символов 0 или 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}.$$$$$$