该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

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

Input Format

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

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

数据范围：

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

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

Output Format

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

5
aabc
abaca
avbvvcvvvd
abcdefg
dabbb

0
1
2
1
1

Source