Folding Strip
Contest: Codeforces Round 941 (Div. 1)
Difficulty rating: 2300
Tags: constructive algorithms, greedy, strings

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 format:
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 format:
For each test case, output a single integer — the minimum possible length of the strip after a valid folding.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

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

Example output:
3
1
3
3
1
2

Editorial:
Define the pattern of a (validly) folded strip to be the set of characters, in order, seen from above after all folds are made.
It is always possible to fold the strip in such a way that no two adjacent characters in the pattern are equal. If we fold in between every pair of equal characters, and don't fold in between every pair of distinct characters, we will achieve this. This diagram shows one example of this (the red lines indicate where to fold, and the final pattern is $$$10101$$$):
This set of folds will always be valid because it ensures that all $$$1$$$s in the original string are on odd indices and all $$$0$$$s are on even indices (or vice versa).
Also, there is only one obtainable pattern (up to reversal) that is alternating in this way. It is never possible to fold in between two adjacent different characters, because that can never be part of a valid folding, and if there exists a pair of adjacent equal characters that you don't fold in between, the pattern will not be alternating.
We can also show that the pattern formed by this process is always optimal. Let $$$t$$$ be any pattern obtained from a valid folding of $$$s$$$. Notice that if we perform a valid fold on $$$t$$$, that corresponds to a valid fold on $$$s$$$, because we can essentially "compose" the valid folding of $$$s$$$ into $$$t$$$ and the valid folding of $$$t$$$ into one valid folding.
So we can fold $$$t$$$ using the process above, which will yield a pattern with alternating characters of length at most $$$len(t)$$$. Because the alternating pattern is unique for a given $$$s$$$, it must be the same (up to reversal) as the one described above. So the above pattern is of size at most $$$len(t)$$$ for any valid pattern $$$t$$$, and is therefore optimal.
We can simulate the folding process to determine the final length.
Complexity: $$$O(n)$$$