题目描述

小慧看到一段由 $n$ 个小写字母组成的字符串 $S$，她想让这个字符串变得尽可能短。她能进行的操作是：可以多次删除 $S$ 中任意一对相邻且不同的字符。例如：如果 $S=$“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$。