有一天,一个富有的商人找到了你。他给了你很多很多金币,让你帮助他来完成任务。
他首先给出了一个字符串,你每次可以花费一个金币来覆盖其中的一个回文串的所有字符。
而商人交给你的任务是让整个字符串的每个字符至少被覆盖一遍。尽可能的省下来金币去买自己喜欢的东西。
所以你就想找到一种花费最少的方案覆盖整个字符串。我相信聪明的你肯定能找到,并且可以求出来最少的花费。
第一行包含一个整数 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