CF1430D.String Deletion

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?

你有一个由 $n$ 个字符组成的字符串 $s$，每个字符均为 0 或 1。

你可以对字符串执行若干次操作。每次操作包含以下两个步骤：

1. 选择一个整数 $i$（取值范围为 $1$ 到当前字符串 $s$ 的长度），然后删除字符 $s_i$（字符串长度减 $1$，其右侧所有字符的下标也相应减 $1$）；
2. 若字符串 $s$ 非空，则删除最长的、由相同字符构成的前缀（剩余字符的下标及字符串长度均减少被删前缀的长度）。

注意：每次操作中，上述两个步骤均为强制执行，且顺序不可调换。

例如，若字符串 $s =$ 111010，则第一次操作可能有如下几种情况：

1. 选择 $i = 1$：111010 $\rightarrow$ 11010 $\rightarrow$ 010；
2. 选择 $i = 2$：111010 $\rightarrow$ 11010 $\rightarrow$ 010；
3. 选择 $i = 3$：111010 $\rightarrow$ 11010 $\rightarrow$ 010；
4. 选择 $i = 4$：111010 $\rightarrow$ 11110 $\rightarrow$ 0；
5. 选择 $i = 5$：111010 $\rightarrow$ 11100 $\rightarrow$ 00；
6. 选择 $i = 6$：111010 $\rightarrow$ 11101 $\rightarrow$ 01。

当字符串 $s$ 变为空时，操作结束。问：最多能执行多少次操作？

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$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，其中每个字符均为 0 或 1。

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

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

对于每个测试用例，输出一个整数——你能执行的最大操作次数。

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.

在第一个测试用例中，例如，你可以选择 $i = 2$，第一次操作后得到字符串 010。之后，你可以选择 $i = 3$，得到字符串 1。最后，你只能选择 $i = 1$，从而得到空字符串。