String Deletion
Contest: Educational Codeforces Round 96 (Rated for Div. 2)
Difficulty rating: 1700
Tags: binary search, data structures, greedy, two pointers

You have a string $$$s$$$ consisting of $$$n$$$ characters. Each character is either 0 or 1.

You can perform operations on the string. Each operation consists of two steps:

1. select an integer $$$i$$$ from $$$1$$$ to the length of the string $$$s$$$, then delete the character $$$s_i$$$ (the string length gets reduced by $$$1$$$, the indices of characters to the right of the deleted one also get reduced by $$$1$$$);
2. if the string $$$s$$$ is not empty, delete the maximum length prefix consisting of the same characters (the indices of the remaining characters and the string length get reduced by the length of the deleted prefix).

Note that both steps are mandatory in each operation, and their order cannot be changed.

For example, if you have a string $$$s =$$$ 111010, the first operation can be one of the following:

1. select $$$i = 1$$$: we'll get 111010 $$$\rightarrow$$$ 11010 $$$\rightarrow$$$ 010;
2. select $$$i = 2$$$: we'll get 111010 $$$\rightarrow$$$ 11010 $$$\rightarrow$$$ 010;
3. select $$$i = 3$$$: we'll get 111010 $$$\rightarrow$$$ 11010 $$$\rightarrow$$$ 010;
4. select $$$i = 4$$$: we'll get 111010 $$$\rightarrow$$$ 11110 $$$\rightarrow$$$ 0;
5. select $$$i = 5$$$: we'll get 111010 $$$\rightarrow$$$ 11100 $$$\rightarrow$$$ 00;
6. select $$$i = 6$$$: we'll get 111010 $$$\rightarrow$$$ 11101 $$$\rightarrow$$$ 01.

You finish performing operations when the string $$$s$$$ becomes empty. What is the maximum number of operations you can perform?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

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

The second line contains string $$$s$$$ of $$$n$$$ characters. Each character is either 0 or 1.

It's guaranteed that the total sum of $$$n$$$ over test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the maximum number of operations you can perform.

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

Note:
In the first test case, you can, for example, select $$$i = 2$$$ and get string 010 after the first operation. After that, you can select $$$i = 3$$$ and get string 1. Finally, you can only select $$$i = 1$$$ and get empty string.

Example input:
5
6
111010
1
0
1
1
2
11
6
101010

Example output:
3
1
1
1
3

Editorial:
Suppose the string consists of $$$n$$$ characters, and each character is different from the adjacent ones (so the string looks like 01010... or 10101...). It's easy to see that we can't make more than $$$\lceil \frac{n}{2} \rceil$$$ operations (each operation deletes at least two characters, except for the case when the string consists of only one character). And there is an easy way to perform exactly $$$\lceil \frac{n}{2} \rceil$$$ operations: always choose the last character and delete it.
Okay, what about the case when some adjacent characters in the string are equal? It's never optimal to delete a character that's different from both adjacent characters: since the second part of each operation always deletes the left block of equal characters, this action merges two blocks, so they will be deleted in one second part of the operation (which decreases the total number of operations).
So, we should always delete a character from a block with at least two equal characters. From which of the blocks, if there are more than one? It's easy to see that we should choose a character from the leftmost such block, since that block is the earliest to be deleted (and if we want to make the same action later, we might be unable to do it).
So, the solution is greedy: during each action, we have to find the leftmost block consisting of at least $$$2$$$ equal characters, and delete a character from it (or the last character of the string, if there are no such blocks). Since the length of the string is up to $$$2 \cdot 10^5$$$ and the number of operations is up to $$$10^5$$$, we should do it efficiently, for example, by storing the eligible blocks in some data structure.