题目描述

小慧看到一段由 $n$ 个小写字母组成的字符串 $S$，她想让这个字符串变得尽可能短。她能进行的操作是：可以多次删除 $S$ 中任意一对相邻且不同的字符。

例如：如果 $S = \text{racoon}$，那么通过删除一对字符，她可以得到字符串 coon、roon、raon、raco，但无法得到 racn（因为被删除的字母是相同的），也没法得到 rcon（因为被删除的字母不是相邻的）。

问：通过进行任意次这种删除操作，小慧能得到的字符串 $S$ 的最小长度是多少？

输入格式

第一行一个整数 $G$，表示有 $G$ 组测试数据。

接下来 $G$ 行，每行一个字符串 $S$。

输出格式

输出 $G$ 行，每行一个整数，表示对应字符串 $S$ 能得到的最小长度。

样例

5
aabc
abaca
avbvvcvvvd
abcdefg
dabbb

0
1
2
1
1

数据范围与提示

• 对于 $40\%$ 的数据，字符串 $S$ 的长度 $\le 10$；
• 对于 $100\%$ 的数据，字符串 $S$ 的长度 $\le 10000$，$G \le 5$。