E. Easiest Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string $$$s$$$ of length $$$n$$$. The score of a string is defined as the number of indices $$$i$$$ such that $$$s_i=s_{i+1}$$$.

The beauty of a string $$$s$$$ is the maximum possible score across all subsequences of $$$s$$$. Find the beauty of string $$$s$$$.

Note that a subsequence of a given string is a sequence that can be derived from the given string by deleting some or no characters without changing the order of the remaining characters.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the size of the string $$$s$$$.

The second line contains the string $$$s$$$, consisting of characters $$$0$$$, $$$1$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print a single integer — the beauty of string $$$s$$$.

Example
Input
3
2
01
5
10110
9
101010101
Output
0
2
4
Note

In second testcase, we are given $$$ s = \text{"10110"} $$$, the score of $$$s$$$ is $$$1$$$ and it's beauty is $$$2$$$, when we take the $$$1$$$st, $$$3$$$rd and $$$4$$$th element as a subsequence.