题目描述

Timur 最初有一个二进制字符串 $s$（长度可能为 $0$）。他进行了若干次（可能为零次）如下操作：

• 在字符串的一端添加一个 $\texttt{0}$，在另一端添加一个 $\texttt{1}$。例如，从字符串 $\texttt{1011}$ 出发，你可以得到 $\color{red}{\texttt{0}}\texttt{1011}\color{red}{\texttt{1}}$ 或 $\color{red}{\texttt{1}}\texttt{1011}\color{red}{\texttt{0}}$。

现在给你 Timur 最终得到的字符串。请你求出他最初可能拥有的字符串的最短长度是多少。

$^{\dagger}$ 二进制字符串是指仅由 $\texttt{0}$ 或 $\texttt{1}$ 组成的字符串（可以为空串）。

输入格式

输入的第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2000$），表示 Timur 最终字符串的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 $\texttt{0}$ 或 $\texttt{1}$ 组成，表示最终的字符串。

输出格式

对于每个测试用例，输出一个非负整数，表示 Timur 最初可能拥有的字符串的最短长度。注意，Timur 最初的字符串可能为空，此时应输出 $0$。

样例

9
3
100
4
0111
5
10101
6
101010
7
1010110
1
1
2
10
2
11
10
1011011010

1
2
5
0
3
1
0
2
4

样例说明

在第一个测试用例中，Timur 最短可能的初始字符串是 $\texttt{0}$，他进行了如下操作：$\texttt{0} \to \color{red}{\texttt{1}}\texttt{0}\color{red}{\texttt{0}}$。

在第二个测试用例中，Timur 最短可能的初始字符串是 $\texttt{11}$，他进行了如下操作：$\texttt{11} \to \color{red}{\texttt{0}}\texttt{11}\color{red}{\texttt{1}}$。

在第三个测试用例中，Timur 最短可能的初始字符串是 $\texttt{10101}$，他没有进行任何操作。

在第四个测试用例中，Timur 最短可能的初始字符串是空串（记作 $\varepsilon$），他进行了如下操作：$\varepsilon \to \color{red}{\texttt{1}}\texttt{}\color{red}{\texttt{0}} \to \color{red}{\texttt{0}}\texttt{10}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{0101}\color{red}{\texttt{0}}$。

在第五个测试用例中，Timur 最短可能的初始字符串是 $\texttt{101}$，他进行了如下操作：$\texttt{101} \to \color{red}{\texttt{0}}\texttt{101}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{01011}\color{red}{\texttt{0}}$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1791C，英文题名 Prepend and Append。