题目描述

你会得到一个二进制字符串。

你需要把这个二进制字符串变成升序排列的二进制字符串，请你找出需要把原字符串分隔成最少的几段才能完成排序。

二进制字符串是由字符0和字符1组成的字符串。

所有字符0位于所有字符1之前的字符串就是升序排序的二进制字符串。

输入

第一行包含一个整数$t(1≤t<500)$--测试用例的数量。 接下来t行，每行包含一个字符串$s(1<|s|<500)$，由字符0和1组成，其中$|s|$表示字符串s的长度。

输出

输出t行，每行一个整数，代表需要分割成这个整数段

样例

6
11010
00000000
1
10
0001111
0110

3
1
1
2
1
2

样例解析

第一个测试用例如上图所示，至少需要分隔成3段。

在第二个和第三个测试用例中，二进制字符串已经排序，所以不需要分隔，一整个字符串即可，相当于就分割成了1段。

在第四个测试用例中，您需要在两个字符之间进行一次分隔，并重新排列它们，所以需要分割成2段。