Timur 起初有一个二进制字符串 $s$（长度可能为 $0$，即允许为空串）。他进行了若干次（也可能为 $0$ 次）如下操作：

• 在字符串的一端添加字符 0，同时在另一端添加字符 1。

例如，从字符串 1011 出发，可以得到 010111（左端加 0、右端加 1），也可以得到 110110（左端加 1、右端加 0）。

现在给出 Timur 的最终字符串。请问他最开始可能拥有的字符串的最短长度是多少？

二进制字符串：只包含字符 0 或 1 的字符串（允许为空串）。

输入格式

• 第一行一个整数 $t$（$1 \le t \le 100$），表示测试用例数量。

• 每个测试用例：

  • 第一行一个整数 $n$（$1 \le n \le 2000$），表示最终字符串长度。
  • 第二行一个长度为 $n$ 的二进制字符串 $s$（只包含 0 和 1），表示最终字符串。

输出格式

对每个测试用例输出一行一个非负整数，表示 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

说明

该操作每次都会在两端分别添加一个 0 和一个 1，因此如果从最终串逆推最短初始串，相当于不断“剥掉”两端字符：只要当前串的首尾字符不同（一个为 0 另一个为 1），就可能是某次操作形成的外层，可以去掉首尾各一个字符；当首尾字符相同则无法继续剥离。最终剩余长度即为答案（可能为 $0$）。