D - Pop and Insert Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

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 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 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 以下

入力

入力は以下の形式で標準入力から与えられる。

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 番目のテストケースに対する答えを出力せよ。

入力例 1

3
5
01001
3
000
15
110010111100101

出力例 1

4
0
16

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 回も必要ありません。

Score : 400 points

Problem Statement

You are given a string S of length N consisting of 0 and 1.

You can perform the following operation on S any number of times (possibly zero):

  • Delete the first or last character, flip it (change 0 to 1 or 1 to 0), and insert it back at any position. More formally, let r(0)= 1 and r(1)= 0, and perform one of the following: (Here, S_i denotes the i-th character of S.)
    • Choose any i\ (1\leq i\leq N) and change S to S_2\dots S_i\,r(S_1)\,S_{i+1}\dots S_N.
    • Choose any i\ (0\leq i\leq N-1) and change S to S_1\dots S_i\,r(S_N)\,S_{i+1}\dots S_{N-1}.

Find the minimum number of operations required to make all characters of S the same. It can be proved that such a sequence of operations always exists.

You are given T test cases, so solve each of them.

Constraints

  • 1\leq T\leq 2\times 10^5
  • 2\leq N \leq 5\times 10^5
  • T and N are integers.
  • S is a string of length N consisting of 0 and 1.
  • The sum of N over all test cases is at most 5\times 10^5.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

\text{case}_i represents the i-th test case. Each test case is given in the following format:

N
S

Output

Output T lines. The i-th line (1\leq i\leq T) should contain the answer for the i-th test case.

Sample Input 1

3
5
01001
3
000
15
110010111100101

Sample Output 1

4
0
16

For the first test case, for example, you can make all characters of S into 0 with four operations as follows. It is impossible to make all characters of S the same with three or fewer operations, so the answer is 4.

  • Delete the first character 0, and insert 1 between the 1st and 2nd characters (in S after deletion). S becomes 11001.
  • Delete the first character 1, and insert 0 between the 2nd and 3rd characters (in S after deletion). S becomes 10001.
  • Delete the last character 1, and insert 0 at the end (in S after deletion). S becomes 10000.
  • Delete the first character 1, and insert 0 at the beginning (in S after deletion). S becomes 00000.

For the second test case, all characters of S are the same from the beginning, so no operation is needed.