题目描述

你会得到一个t，代表t个测试样例，每个测试样例都有一个长度为n的，并且只由0和1组成的字符串s。

		A(s)是s这个字符串的子串与”01”相等的个数。B(s)是s这个字符串的子串与”10”相等的个数。例如"010"这个字符串，它的A(s)=1,B(s)=1。
	
	
		小匡最喜欢平衡了，所以它希望s这个字符串中的A(s)和B(s)相等。现在你可以修改这个字符串(0改成1，或者1变成0)，使这个字符串的A(s)和B(s)相等。现在憨憨想要请你帮他想想最少修改几次可以使A(s)和B(s)相等。

输入格式

输出格式

3
1
01
010

0
1
0