AT_arc156_a [ARC156A] Non-Adjacent Flip

[problemUrl]: https://atcoder.jp/contests/arc156/tasks/arc156_a $ 1 $ から $ N $ の番号がついた、表裏が区別できるコインが $ N $ 枚あります。コインの表裏は長さ $ N $ の文字列 $ S $ で表され、$ S $ の $ i $ 番目の文字が `1` のときコイン $ i $ は表を向いており、`0` のときコイン $ i $ は裏を向いています。 あなたは、以下の操作を $ 0 $ 回以上好きな回数繰り返すことができます。 - $ 1\leq\ i\

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ ​ 各ケースは以下の形式で与えられる。 > $ N $ $ S $

$ T $ 行出力せよ。$ i\ (1\leq\ i\ \leq\ T) $ 行目には、 $ i $ 番目のテストケースについて、操作によりコインを全て裏向きにできる場合は必要な操作回数の最小値を、できない場合は `-1` を出力せよ。

### 制約 - $ 1\ \leq\ T\ \leq\ 2\times\ 10^5 $ - $ 3\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ S $ は `0`, `1` からなる長さ $ N $ の文字列 - 入力される数値は全て整数 - $ 1 $ つの入力に含まれるテストケースについて、$ N $ の総和は $ 2\times\ 10^5 $ 以下 ### Sample Explanation 1 $ 1 $ 番目のテストケースについては、$ (i,j)=(1,3) $ として操作を $ 1 $ 回行うと、$ 1 $ 回の操作でコインを全て裏向きにできます。 $ 2 $ 番目のテストケースについては、$ (i,j)=(1,3) $ として操作を $ 1 $ 回行い、$ (i,j)=(4,6) $ として操作を $ 1 $ 回行うと、$ 2 $ 回の操作でコインを全て裏向きにできます。 $ 3 $ 番目のテストケースについては、コインを全て裏向きにできないことが証明できるので、`-1` を出力してください。 $ 4 $ 番目のテストケースについては、コインは既に全て裏向きなので、操作は必要ありません。