AT_abc426_d [ABC426D] Pop and Insert

`0` および `1` からなる長さ $ N $ の文字列 $ S $ が与えられます。 あなたは $ S $ に対して以下の操作を好きな回数（ $ 0 $ 回でもよい）行うことができます。 - 先頭または末尾の $ 1 $ 文字を削除し、その文字を反転して（`0` ならば `1` に、`1` ならば `0` に変えて）、好きな位置に挿入し直す。 より厳密には、 $ r( $ `0` $ )= $ `1` $ ,r( $ `1` $ )= $ `0` として、以下のいずれかを行う。(ここで、 $ S_i $ は $ S $ の $ i $ 文字目を表す。) - 好きな $ i\ (1\leq i\leq N) $ を選んで、 $ S $ を $ S_2\dots S_i\,r(S_1)\,S_{i+1}\dots S_N $ に変更する。 - 好きな $ i\ (0\leq i\leq N-1) $ を選んで、 $ S $ を $ S_1\dots S_i\,r(S_N)\,S_{i+1}\dots S_{N-1} $ に変更する。 $ S $ の全ての文字を同じ文字にするために必要な操作回数の最小値を求めてください。 なお、そのような操作列が必ず存在することは証明可能です。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

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

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

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、例えば以下のように $ 4 $ 回の操作をすることで $ S $ の全ての文字を `0` にすることができます。 $ 3 $ 回以下の操作で $ S $ の全ての文字を同じ文字にすることはできないので、答えは $ 4 $ です。 - 先頭の文字 `0` を削除し、`1` を（削除した後の $ S $ における） $ 1 $ 文字目と $ 2 $ 文字目の間に挿入する。 $ S= $ `11001` になる。 - 先頭の文字 `1` を削除し、`0` を（削除した後の $ S $ における） $ 2 $ 文字目と $ 3 $ 文字目の間に挿入する。 $ S= $ `10001` になる。 - 末尾の文字 `1` を削除し、`0` を（削除した後の $ S $ における）末尾に挿入する。 $ S= $ `10000` になる。 - 先頭の文字 `1` を削除し、`0` を（削除した後の $ S $ における）先頭に挿入する。 $ S= $ `00000` になる。 $ 2 $ 番目のテストケースについて、はじめから $ S $ の全ての文字が同じ文字であるため、操作は $ 1 $ 回も必要ありません。 ### Constraints - $ 1\leq T\leq 2\times 10^5 $ - $ 2\leq N \leq 5\times 10^5 $ - $ T,N $ は整数 - $ S $ は `0` および `1` からなる長さ $ N $ の文字列 - 全てのテストケースにおける $ N $ の総和は $ 5\times 10^5 $ 以下