Turning Off the Bulbs

You are given several test cases. In each test case, you are given an integer n and a binary string of length n representing bulbs. Each character in the string is either '1' (bulb is on) or '0' (bulb is off).

In one operation, you can choose any consecutive sequence of bulbs that are on (i.e., consecutive '1's) and turn them off. Your task is to determine the minimum number of operations required to turn off all the bulbs for each test case.

Note: It is always optimal to turn off the longest contiguous segments of '1's in each operation.

inputFormat

The first line contains an integer T, the number of test cases.

Each test case consists of two lines:

• The first line contains an integer n, the number of bulbs.
• The second line contains a binary string of length n representing the state of the bulbs.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of operations required to turn off all the bulbs.

1
5
11001

2