AT_abc408_d [ABC408D] Flip to Gather

長さ $ N $ の `0` と `1` のみからなる文字列 $ S $ が与えられます。 あなたは以下の操作を何回でも( $ 0 $ 回でもよい)行うことができます。 - $ 1 \leq i \leq N $ を満たす整数 $ i $ を選び、 $ S_i $ が `0` のときは `1` に、`1` のときは `0` に変更する。 あなたの目標は $ S $ に含まれる `1` が**高々 $ 1 $ 個**の区間をなすようにすることです。目標を達成するために必要な操作回数の最小値を求めてください。 より厳密には以下の条件をともに満たすような整数の組 $ (l,r) $ が存在するような $ S $ にすることが目標です。目標を達成するために必要な操作回数の最小値を求めてください。 - $ 1 \leq l \leq r \leq N+1 $ - $ 1 \leq i \leq N $ を満たす整数 $ i $ に対し、 $ S_i= $ `1` と $ l \leq i < r $ は同値である。 なお、有限回の操作で必ず目標が達成できることが証明できます。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \textrm{case}_1 $ $ \textrm{case}_2 $ $ \vdots $ $ \textrm{case}_T $ $ \textrm{case}_i $ は $ i $ 番目のテストケースを表し、以下の形式で与えられる。 > $ N $ $ S $

$ T $ 行出力せよ。 $ i $ 行目 $ (1 \leq i \leq T) $ には $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースにおいて、 $ S_1 $ を `0` に変更する操作を行なうと、`1` が $ 1 $ 個の区間をなすようになります。また、 $ S $ のままでは条件を満たしていません。したがって、答えは $ 1 $ です。 $ 2 $ 番目のテストケースにおいて、 $ S $ に `0` が $ 1 $ 個もないので、操作を行う必要はありません。したがって答えは $ 0 $ です。 $ 3 $ 番目のテストケースにおいて、 $ S $ に `1` が $ 1 $ 個もないので、操作を行う必要はありません。したがって答えは $ 0 $ です。 ### Constraints - $ 1 \leq T \leq 20000 $ - $ 1 \leq N \leq 2 \times 10^5 $ - $ S $ は `0` と `1` のみからなる長さ $ N $ の文字列 - 各入力ファイルについて、すべてのテストケースの $ N $ の総和は $ 2 \times 10^5 $ 以下である。 - $ T,N $ は整数