题目描述

给定一个由 $012$ 构成的字符串 S，你可以执行以下三种操作任意次

1. 将任意一个 $2$ 字符修改为 0 或者 1。
2. 选择相邻的 $2$ 个 $0$ 字符，将它们同时删除。
3. 选择相邻的 $2$ 个 $1$ 字符，将它们同时删除。

要求最小化 $|S|$ 的最终大小，即最小化 $S$ 字符串的长度。

输入格式

第一行一个正整数 $T$ 表示数据组数，之后对于每组数据：
输入第一行，一个字符串 $S$。

输出格式

对于每组数据，输出一行，表示答案。

数据范围与提示

对于 $100\%$ 的数据，$S$ 的长度之和不超过 $10^6$。