题目描述

你有一个由 $1$ 和 $0$ 构成的字符串 $s$。

你需要先从 $s$ 的开头移除若干字符，然后从 $s$ 的结尾移除若干字符。（当然，你可以不移除任何字符，也可以将整个 $s$ 移除掉）这样做的代价是从 $s$ 中移除的 $1$ 的个数和 $s$ 中剩余的 $0$ 的个数的最大值。

求代价的最小值。

输入格式

第一行一个整数 $t$ 表示数据组数。$(1\le t\le 10^4)$

接下来 $t$ 行，每行一个字符串 $s$ 表示这组数据的 $s$。$(1\le |s|\le 2⋅10^5)$

$s$ 的总和不超过 $2⋅10^5$。

输出格式

对于每组数据，输出一个整数表示最小代价。

样例

5
101110110
1001001001001
0000111111
00000
1111

1
3
0
0
0

样例解释：

101110110 -> (10) 111011 (0)

1001001001001 -> (100100) 1001 (001)

0000111111 -> (0000) 111111 ()

00000 -> (00000)()

1111 -> ()1111()