#815. 147的字符串

147的字符串

题目描述

147学长最近获得了一个由字符 0 和 1 组成的字符串S。他对这个字符串很是喜爱,以至于他总想对这个字符串做点什么

于是,147想到了一个骚操作:

147从字符串的开头删除了几个(可能是零个)字符,然后又从字符串的末尾删除了几个(可能是零个)字符。删除后,字符串可能会变为空。147是一个做事总是考虑成本的人,所以他定义删除的成本是以下两个值中的最大值

  • 字符串中剩余的字符0的个数;
  • 从字符串中删除的字符1的个数。

请问147可以达到的最小删除成本是多少?

输入形式

第一行包含一个整数t (1t51031\leq t\leq5*10^3) — 测试用例的数量。

每个测试用例由一行由一个字符串S组成(1S21051\leq |S|\leq2*10^5),由字符 0 和 1 组成。

|S|表示字符串S的长度

保证每个测试样例的字符串的总长度不会超过21052*10^5

输出形式

对于每个测试用例,打印一个整数 — 147可以实现的最小删除成本。

样例

5
101110110
1001001001001
0000111111
00000
1111
1
3
0
0
0

样例解释

在第一个测试用例中,可以从开头删除两个字符,从末尾删除一个字符。只有一个 1 被删除,只剩下一个 0,所以成本是1;

在第二个测试用例中,可以从开头删除三个字符,从末尾删除六个字符。保留两个字符 0,删除三个字符 1,因此成本为3;

在第三个测试用例中,最好从开头删除四个字符;

在第四个测试用例中,最好删除整个字符串;

在第五个测试用例中,最好将字符串保持原样。