求01反转次数

题目描述

Yuilice最近给学生们上了一节动态规划的课程，为了让各位同学了解到动态规划的核心内容是划分阶段与建立状态转移方程，于是他出了这一道题。

Yuilice会给各位同学一个字符串$S$，这个字符串$S$只会由字符$0$与字符$1$组成，Yuilice可以对这个字符串进行一些操作，操作的内容如下。

• Yuilice可以选中下标为$i(1 \leq i \leq S.length)$的字符，将位于下标$i$后的所有字符$i \leq j \leq S.length$全部变为相反的数，例如0全部变成1，1全部变成0。

现在，Yuilice想知道，他最少需要几次操作，才可以将字符串$S$变为不递减的字符串？

输入格式

第一行输入一个正整数$t(1 \leq t \leq 10^4)$，代表接下来有$t$组样例测试。

随后$t$行，每行给出一个数字$n(1 \leq n \leq 10^5)$，代表字符串$S$的长度。

输出格式

每一组样例，输出一个整数代表其最少操作次数

样例 #1

样例输入 #1

5
1
1
3
101
5
10101
10
1010101010
7
0001000

样例输出 #1

0
2
4
9
1

提示

NOTE

第一组样例当中，字符串本身便不是递减的。

第二组样例当中，我们需要在$i = 2$的时候转变字符串后两个字符变为$10$，于$i = 3$的时候转变后一个字符为$1$，最后将字符串变为$111$则可完成。