题目描述

有一个只含 $\texttt{0}$ 和 $\texttt{1}$ 的字符串 $s$，你可以对它进行如下两种操作：

1. 耗费一个金币，从 $s$ 中删除 $1$ 个字符。

2. 将 $s$ 中任意两字符互换位置（免费）。

定义一个字符串 $t$ 是美的代表对于所有满足 $1 \le i \le \left|t\right|$ 的 $i$，$s_i \ne t_i$ 。

你可以进行任意多次操作，假设 $s$ 修改后变为了 $s'$，问最少花费多少金币能使最终得到的 $s'$ 是美的。

输入格式

本题单测试点内有多组数据。

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

接下来的 $t$ 行，每行一个字符串 $s$。$(1 \le \left|s\right| \le 2 \times 10^5,s_i \in \{\texttt{0},\texttt{1}\})$。

输出格式

对于每一组数据，输出一行，为最少花费的金币数。

样例

4
0
011
0101110001
111100

1
1
0
4