Problem Description

bjh has a string $s$ of length $n$ that consists only of the characters 0 and 1.

In each operation, bjh can choose a maximal substring of length greater than $1$ that contains only one kind of character, and change the whole substring into the opposite character (for example, after one operation, $11001$ can become $0001$ or $1111$).

bjh will keep operating until the string can no longer be operated on. Please find, among all possible operation sequences, the difference between the maximum number of operations and the minimum number of operations.

Input Format

This problem contains multiple test cases. The first line contains an integer $T$ $(1\leq T\leq 10^4)$, the number of test cases.

For each test case, the first line contains an integer $n$ $(1\leq n\leq 10^5)$, the length of the string.

The second line contains a string $s$, the initial string.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output Format

For each test case, output an integer, the difference between the maximum number of operations and the minimum number of operations.

2
5
11001
5
11000

1
0

Hint

Translated by ChatGPT 5