C. Prepend and Append

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Timur initially had a binary string†† s� (possibly of length 00). He performed the following operation several (possibly zero) times:

• Add 00 to one end of the string and 11 to the other end of the string. For example, starting from the string 10111011, you can obtain either 010111010111 or 110110110110.

You are given Timur's final string. What is the length of the shortest possible string he could have started with?

†† A binary string is a string (possibly the empty string) whose characters are either 00 or 11.

Input

The first line of the input contains an integer t� (1≤t≤1001≤�≤100) — the number of testcases.

The first line of each test case contains an integer n� (1≤n≤20001≤�≤2000) — the length of Timur's final string.

The second line of each test case contains a string s� of length n� consisting of characters 00 or 11, denoting the final string.

Output

For each test case, output a single nonnegative integer — the shortest possible length of Timur's original string. Note that Timur's original string could have been empty, in which case you should output 00.

Example

input

Copy

9

3

100

4

0111

5

10101

6

101010

7

1010110

1

1

2

10

2

11

10

1011011010

output

Copy

1
2
5
0
3
1
0
2
4

Note

In the first test case, the shortest possible string Timur started with is 00, and he performed the following operation: 0→1000→100.

In the second test case, the shortest possible string Timur started with is 1111, and he performed the following operation: 11→011111→0111.

In the third test case, the shortest possible string Timur started with is 1010110101, and he didn't perform any operations.

In the fourth test case, the shortest possible string Timur started with is the empty string (which we denote by ε�), and he performed the following operations: ε→10→0101→101010�→10→0101→101010.

In the fifth test case, the shortest possible string Timur started with is 101101, and he performed the following operations: 101→01011→1010110101→01011→1010110.

解题说明：水题，只需要判断字符串头尾是否一样，如果一样就无法裁剪，否则去除头尾，直到无法找到头尾不一样的情况。

#include <stdio.h>int main()
{int t;scanf("%d", &t);while (t--){int n;scanf("%d", &n);char s[2002];scanf("%s", s);int ans = n;int l = 0, r = n - 1;while (l < r && s[l] != s[r]){ans -= 2;l++;r--;}printf("%d\n", ans);}return 0;
}