题目描述

给定一个由字符 0 和 1 组成的长度为 $N$ 的字符串 $S$。

你可以对 $S$ 任意次（可能为 $0$ 次）执行以下两个操作之一：

• 将第一个字符删除并翻转后插入到任意位置；或者
• 将最后一个字符删除并翻转后插入到任意位置。

更形式地，定义翻转函数 $r$ 为 $r(0)=1$ 且 $r(1)=0$。设 $S_i$ 表示字符串 $S$ 的第 $i$ 个字符（从 $1$ 开始编号）。操作可以是以下两种之一：

1. 任选 $i$（$1\le i\le N$），将 $S$ 变为$$S_2S_3\ldots S_i, r(S_1), S_{i+1}\ldots S_N.$$
2. 任选 $i$（$0\le i\le N-1$），将 $S$ 变为$$S_1S_2\ldots S_i, r(S_N), S_{i+1}\ldots S_{N-1}.$$

请你求使 $S$ 中的所有字符都相同所需的最小操作次数。已知对于任意输入，总存在一系列操作可以实现该目标。

你需要处理 $T$ 个测试用例。

输入格式

输入包含多组测试用例。

• 第一行包含一个整数 $T$，表示测试用例数。
• 每个测试用例包含两行，第一行为整数 $N$，第二行为字符串 $S$。

输出格式

输出 $T$ 行，第 $i$ 行为第 $i$ 个测试用例的答案（使字符串所有字符相同所需的最少操作次数）。

样例输入

3
5
01001
3
000
15
110010111100101

样例输出

4
0
16

说明

样例解释

对于第一个测试用例，您可以通过以下四次操作将 $S$ 中的所有字符变为 0。不可能通过三次或更少的操作将 $S$ 中的所有字符变成相同的字符，因此答案是 $4$ 。

• 删除第一个字符 0，并在第一个和第二个字符之间插入 1（删除后的 $S$ 中）。 $S$ 变为 11001。
• 删除第一个字符 1，并在第二个和第三个字符之间插入 0（在删除后的 $S$ 中）。 $S$ 变为 10001。
• 删除最后一个字符 1，并在末尾插入 0（删除后位于 $S$ 中）。 $S$ 变成 10000。
• 删除第一个字符 1，并在开头插入 0（在删除后的 $S$ 中）。 $S$ 变成 00000。

对于第二个测试用例， $S$ 的所有字符从一开始就是相同的，因此无需进行任何操作。

数据范围

• $1\le T\le 2\times 10^5$；
• $2\le N\le 5\times 10^5$；
• $S$ 为长度为 $N$ 的字符串，仅包含字符 0 和 1；
• 所有 $N$ 的总和（对所有测试用例）不超过 $5\times 10^5$。