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}}$$$。