给定一个偶数长度的字符串s。字符串s是二进制字符串，即串中只包含0和1。字符串s有n/2个0和n/2个1 (n是偶数)。牛娃可以反转s中的任何子串作为一次操作。字符串的子串是该字符串的连续子序列。 

现规定交替字符串如下：串中任意两个相邻字符的值都不相等，即对于所有i，如果s_i≠s_i+1，则称该字符串为交替字符串。通常有两种类型的交替字符串:01010101… 或10101010…  。相反，0110，1101010100，101011110000等字符串都不是交替字符串。

    请问，牛娃将字符串s转换为交替字符串的最小操作次数是多少? 

第一行包含一个整数t(1≤t≤1000)，为测试用例的数量。  

每个测试用例的第一行包含单个整数n(2≤n≤10⁵; n为偶数)，表示字符串s的长度。  

每个测试用例的第二行包含一个长度为n (s_i∈{0,1})的二进制字符串s。 字符串s有n/2个0和n/2个1。  

对于每个测试用例，输出一个整数（每个测试用例占一行），表示使二进制串s转换为交替字符串的最少操作次数。

3
2
10
4
0110
8
11101000

0
1
2

在第一个测试用例中，字符串10已经是交替字符串。 

在第二个测试用例中，我们可以反转s的最后两个元素，得到:0110→0101。 

在第三个测试用例中，我们可以进行以下两种操作:   

11101000→10101100; 

10101100→10101010。