Let $n$ be a positive integer. Mario has a binary string$^{\text{∗}}$ $s$ of length $n$. In one move, he can choose any position $i$ ($2 \leq i \leq n-1$) such that it's between two 1's, i.e., $s_{i-1} = s_{i+1} = \texttt{1}$, and then set $s_i$ to either 0 or 1.
Mario can perform this operation as many times as he wants (possibly zero). What's the minimum and maximum number of 1's that can be in the resulting string?
$^{\text{∗}}$A binary string is a string whose characters are either 0 or 1.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.
The first line of each test case contains an integer $n$ ($3 \leq n \leq 100$) — the length of the string.
The second line of each test case contains a string $s$ of length $n$ consisting of characters 0 or 1.
Output
For each test case, output two integers — the minimum and maximum number of 1's in the resulting string after some number of moves.
Note
In the first test case, the minimum number of 1's that can be in the resulting string is $2$. This is done by transforming the string as follows: $$\mathtt{1}\underline{\mathtt{1}}\mathtt{1} \to \mathtt{101}.$$ The maximum number of 1's that can be in the resulting string is $3$, by doing nothing.
In the second test case, the minimum number of 1's that can be in the resulting string is $3$. This is done by transforming the string as follows: $$\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}.$$ The maximum number of 1's that can be in the resulting string is $5$. This is done by transforming the string as follows: $$\mathtt{011}\underline{\mathtt{0}}\mathtt{11} \to \mathtt{011111}.$$
样例
4
3
111
6
011011
7
1011101
9
100101101
2 3
3 5
4 7
5 7
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。