E. Maximal Substring Flipping
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

bjh can choose a maximal substring of length greater than $$$1$$$ that consists of only one type of character, and change the entire substring to the opposite character (for example, in the string $$$11001$$$, after one operation it can be changed to $$$0001$$$ or $$$1111$$$).

bjh will continue to operate until the string can no longer be modified. Please help him find the difference between the maximum and minimum number of operations in all operation scenarios.

Input

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

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

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

It is guaranteed that the sum of all $$$n$$$ in the input does not exceed $$$10^6$$$.

Output

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

Example
Input
2
5
11001
5
11000
Output
1
0