题目描述

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




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

输入格式

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




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




 




**数据范围：** 




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




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

输出格式

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

样例

输入

5
aabc
abaca
avbvvcvvvd
abcdefg
dabbb

输出

0
1
2
1
1

来源

南海区赛 2024南海小学