AT_tupc2024_e 010-11 Shorten

長さ $ N $ の `0`, `1`からなる文字列 $ S $ が与えられます。 文字列 $ S $ に対して以下の $ 2 $ 種類の操作を繰り返し行うことができます。 - 操作 $ 1 $ ： $ S $ の中の連続部分文字列 `010` を $ 1 $ つ選び、 `1` に置き換える。 - 操作 $ 2 $ ： $ S $ の中の連続部分文字列 `11` を $ 1 $ つ選び、 `1` に置き換える。 操作を行うことができる回数の最大値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ それぞれのテストケースは次の形式で与えられる。 > $ N $ $ S $

$ T $ 行出力せよ。 $ i=1,2,\dots,T $ に対して $ i $ 行目には $ i $ 番目のテストケースの答えを整数で出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、例えば以下のように $ 3 $ 回の操作を行うことができます。 - `010100` の $ 3 $ から $ 5 $ 文字目の `010` を `1` に置き換え、`0110` にする。 - `0110` の $ 2 $ から $ 3 $ 文字目の `11` を `1` に置き換え、`010` にする。 - `010` の $ 1 $ から $ 3 $ 文字目の `010` を `1` に置き換え、`1` にする。 `010100` に対して $ 4 $ 回以上の操作を行うことはできないため、答えは $ 3 $ となります。 ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 1 \leq N \leq 10^6 $ - $ S $ は `0`, `1` からなる長さ $ N $ の文字列 - $ 1 $ つの入力ファイルに含まれる $ N $ の総和は $ 10^6 $ 以下 - $ T,N $ は整数