問題文

長さ N の 0, 1からなる文字列 S が与えられます。
文字列 S に対して以下の 2 種類の操作を繰り返し行うことができます。

• 操作 1：S の中の連続部分文字列 010 を 1 つ選び、 1 に置き換える。

• 操作 2：S の中の連続部分文字列 11 を 1 つ選び、 1 に置き換える。

操作を行うことができる回数の最大値を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^6
• S は 0, 1 からなる長さ N の文字列
• 1 つの入力ファイルに含まれる N の総和は 10^6 以下
• T,N は整数

入力例 1

5
6
010100
4
0110
3
100
2
00
20
01001100000001101001

出力例 1

3
2
0
0
11

1 つ目のテストケースについて、例えば以下のように 3 回の操作を行うことができます。

• 010100 の 3 から 5 文字目の 010 を 1 に置き換え、0110 にする。
• 0110 の 2 から 3 文字目の 11 を 1 に置き換え、010 にする。
• 010 の 1 から 3 文字目の 010 を 1 に置き換え、1 にする。

010100 に対して 4 回以上の操作を行うことはできないため、答えは 3 となります。