有一天，一个富有的商人找到了你。他给了你很多很多金币，让你帮助他来完成任务。
他首先给出了一个字符串，你每次可以花费一个金币来覆盖其中的一个回文串的所有字符。
而商人交给你的任务是让整个字符串的每个字符至少被覆盖一遍。尽可能的省下来金币去买自己喜欢的东西。
所以你就想找到一种花费最少的方案覆盖整个字符串。我相信聪明的你肯定能找到，并且可以求出来最少的花费。
第一行包含一个整数 t ，表示有 t 组数据。 接下来 t 行每行一个字符串 s ， s 的长度不超过 10^6 。
对于每组数据输出一个整数，表示覆盖住整个字符串需要的最少花费。
1 aabcbaabbcbbaxx
3
对于 10\% 的数据， s 的长度不超过 100 ；
对于 20\% 的数据， s 的长度不超过 1000 ；
对于 100\% 的数据， 0 \leq t \leq 32 ， s 的长度不超过 10^6