题目描述

小慧看到一段由 $n$ 个小写字母组成的字符串 $S$，她想让这个字符串变得尽可能短。她能进行的操作是：可以多次删除 $S$ 中任意一对相邻且不同的字符。例如：如果 $S=“racoon”$，那么通过删除一对字符，他可以得到字符串 $“coon”、“roon”、“raon”、“raco”$，但无法得到 $“racn”$（因为被删除的字母是相同的），也没法得到 $“rcon”$（因为被删除的字母不是相邻的）。 问：通过进行任意次这种删除操作，小慧能得到的字符串 $S$ 的最小长度是多少？

输入描述

第一行一个整数 $G$，表示有 $G$ 组测试数据； 接下来 $G$ 行，每行一个字符串 $S$；

输出描述

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

用例输入 1

5
aabc
abaca
avbvvcvvvd
abcdefg
dabbb

用例输出 1

0
1
2
1
1

提示

数据范围： 对于 40% 的数据，字符串 S 的长度<=10；

对于 100% 的数据，字符串 S 的长度<=10000，G<=5。