← 返回题目列表

Codeforces · 1791/C

C. 前置和附加

中文机器翻译题面 查看原题

Timur 最初有一个二进制字符串$$$^{\dagger}$$$ $$$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}}$$$。

$$$^{\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$$$。

示例

输入 #1

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

输出 #1

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}} \至\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{红色}{\texttt{1}}\texttt{01011}\color{红色}{\texttt{0}}$$$。