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:
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:
You finish performing operations when the string $$$s$$$ becomes empty. What is the maximum number of operations you can perform?
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$$$.
For each test case, print a single integer — the maximum number of operations you can perform.
5 6 111010 1 0 1 1 2 11 6 101010
3 1 1 1 3
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.
Name |
---|