You are given a binary string of length $n$. You are asked to convert the given string in the format such that no two zeros or no two ones are together in the string.

You are allowed to perform the operation:

• Select any substring of length 2 and make it change to any required substring.

Find the minimum number of moves required to convert the string in the required format.

A binary string is a string consisting of only zeros and ones.

Input format

• The first line of input contains one integer $t$ denoting the number of test cases. Each test case consists of two lines.
  • The first line denotes the length of the string and
  • The second line will be a binary string.

Output format 

Print the minimum number of operations required to change a provided string into the required string format.

Constraints

$1 \le t \le 1000$

$1 \le n \le 1000$