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}.$$

Samples

4
3
111
6
011011
7
1011101
9
100101101

2 3
3 5
4 7
5 7