题目描述

光头强最初有一个二进制字符串 $s^†$（长度可能为 $0$）。他多次（可能为零）执行以下操作：

在字符串的一端添加 0，在字符串的另一端添加 1。例如，从字符串 1011 开始，可以获得 010111 或 110110。

给你被光头强的处理过后的字符串。请你求出初始串的最短长度。

$^†$ 二进制字符串是字符为 0 或 1 的字符串（可能是空字符串）。

输入格式

输入的第一行包含一个整数 $t(1≤t≤100)$ 代表测试用例的数量。

每个测试用例的第一行包含一个整数 $n(1≤n≤2000)$ 代表光头强的最终字符串的长度。

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

输出格式

对于每个测试用例，输出一个非负整数代表初始字符串的最短长度。请注意，初始字符串可能为空，在这种情况下，您应该输出 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

样例说明

在第一个测试用例中，初始的最短字符串是0，光头强执行了以下操作：0→100

在第二个测试用例中，初始的最短字符串是11，光头强执行了以下操作：11→0111

在第三个测试用例中，初始的最短字符串是10101，光头强没有执行任何操作。

在第四个测试用例中，初始的最短可能字符串是空字符串（我们用 ε 表示），光头强执行了以下操作：ε→10→0101→101010

在第五个测试用例中，初始的最短字符串是101，光头强执行了以下操作：101→01011→1010110