小W同学收到一个生日礼物，几个稀有金属片组成的链子，每串链子有多个金属片组成，每个金属片有黑白两个面，挂在墙上做装饰还蛮好看的。
一开始的颜色是打乱的，小W同学想把所有的金属片整理一下：尽量同一种颜色放在一起；整体看起来全部白色或者全部黑色，或者从白到黑。（为了不至于显得头重脚轻，不要把白色的放在黑色的下面。）
不过翻转上面的金属片时，下面的金属片都会跟着一起翻转。他想问问你，最少要翻转几次能完成整理。
这个故事讲的是二进制字符串。二进制字符串是仅由字符0和1组成的字符串。
你将收到一个长度为n的二进制字符串s1s2…sn，然后请用最少次数的翻转操作使其变为单调不减。
1、“单调不减”的意思是说：每个字符应不小于前一个字符。比如最后的结果“00”、“01”、“11”是允许的，“10”是不允许的。
2、每次的“翻转操作”定义为：从任意位置开始到串末尾结束，将每个位置的值更改为相反的值，即：如果si=1，则使si=0，反之亦然。
第1行，整数m（1≤m≤100)，表示有m个这样的二进制字符串。
接下来m行，每行一个空格隔开的整数n（1≤n≤100000）和二进制串s。
4
1 1
2 10
3 101
6 1000100
1
2
3
【样例解释】
一共4个样例。
在第一个样例中，字符串已经是非递减的，所以答案是0次。
在第二个样例中，可以选择第1个字符开始到结尾，s=01，答案是1次。
在第三个样例中，您可以选择第1个到结尾，得到s=010，然后选择第2个到结尾。得到s=001，即一个非递减字符串，答案是2次。
在第四个样例中，您可以选择第5个到结尾，得到s=100001。然后选择第2个到结尾，得到s=111110。然后我们选择第1个到结尾，得到非递减字符串s=000001，答案是3次。
【数据规模】
40%的数据，m≤10，n≤10；
其中10%的数据，串中只有一个0或1。
70%的数据，m≤50，n≤100；
100%的数据，m≤100，n≤100000。