311291: CF1966E. Folding Strip

E. Folding Striptime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have a strip of paper with a binary string $s$ of length $n$. You can fold the paper in between any pair of adjacent digits.

A set of folds is considered valid if after the folds, all characters that are on top of or below each other match. Note that all folds are made at the same time, so the characters don't have to match in between folds.

For example, these are valid foldings of $s = \mathtt{110110110011}$ and $s = \mathtt{01110}$:

The length of the folded strip is the length seen from above after all folds are made. So for the two above examples, after the folds shown above, the lengths would be $7$ and $3$, respectively.

Notice that for the above folding of $s = \mathtt{01110}$, if we made either of the two folds on their own, that would not be a valid folding. However, because we don't check for validity until all folds are made, this folding is valid.

After performing a set of valid folds, what is the minimum length strip you can form?

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$) — the size of the strip.

The second line of each test case contains a string $s$ of $n$ characters '0' and '1' — a description of the digits on the strip.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output a single integer — the minimum possible length of the strip after a valid folding.

ExampleInput

6
6
101101
1
0
12
110110110011
5
01110
4
1111
2
01

Output

3
1
3
3
1
2

Note

For the first example case, one optimal folding is to fold the strip in the middle, which produces a strip of length 3.

The third and fourth example cases correspond to the images above. Note that the folding shown above for $s = \mathtt{110110110011}$ is not of minimal length.

题目大意：
你有一张带有长度为n的二进制字符串s的纸条。你可以在任意两个相邻数字之间折叠这张纸。

一组折叠被认为是有效的，如果在折叠之后，所有上下对齐的字符都匹配。注意，所有折叠是同时进行的，所以字符在折叠之间不需要匹配。

例如，这是s = 110110110011和s = 01110的有效折叠：

在所有折叠完成后的从上方看到的长条长度即为折叠后的长度。所以对于上面的两个例子，折叠后的长度分别是7和3。

请注意，对于s = 01110的上述折叠，如果我们只进行两个折叠中的任何一个，那将不是一个有效的折叠。但是，因为我们要在所有折叠完成后才检查有效性，所以这个折叠是有效的。

在进行一组有效折叠后，你能形成的最小长度纸条是多少？

输入数据格式：
第一行输入包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——纸条的长度。

每个测试用例的第二行包含一个由n个字符'0'和'1'组成的字符串s——纸条上数字的描述。

保证所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出一个整数——有效折叠后纸条的最小可能长度。题目大意： 你有一张带有长度为n的二进制字符串s的纸条。你可以在任意两个相邻数字之间折叠这张纸。 一组折叠被认为是有效的，如果在折叠之后，所有上下对齐的字符都匹配。注意，所有折叠是同时进行的，所以字符在折叠之间不需要匹配。 例如，这是s = 110110110011和s = 01110的有效折叠： 在所有折叠完成后的从上方看到的长条长度即为折叠后的长度。所以对于上面的两个例子，折叠后的长度分别是7和3。 请注意，对于s = 01110的上述折叠，如果我们只进行两个折叠中的任何一个，那将不是一个有效的折叠。但是，因为我们要在所有折叠完成后才检查有效性，所以这个折叠是有效的。 在进行一组有效折叠后，你能形成的最小长度纸条是多少？ 输入数据格式： 第一行输入包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——纸条的长度。 每个测试用例的第二行包含一个由n个字符'0'和'1'组成的字符串s——纸条上数字的描述。 保证所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一个整数——有效折叠后纸条的最小可能长度。