一份字符串是回文，如果从左往右和从右往左看是一样的。例如，“abcabacba”是一个回文串，“dbcaabd”则不是一个回文串。
我们可以通过切割，把一个字符串分成回文串。
比如，字符串"abc"，通过切割两次可以变为回文，也即分割为a,b,c
再比如，对于字符串“abaacca”，最少切割一次，就可以得到“aba”和“acca”这两个回文子串。
现在读者朋友想知道他最少切割多少次就可以达到目的。

输入的第一行是一个整数 T (T <= 20) ，表示一共有 T 组数据。
 接下来的 T 行，每一行都包含了一个长度不超过的 1000 的字符串，且字符串只包含了小写字母。

对于每组数据，输出一行。该行包含一个整数，表示阿福最少切割的次数，使得切割完得到的子串都是回文的。

提示：
对于第一组样例，最少切割 1 次，将原串切割为“aba”和“acca”两个回文子串。 
对于第二组样例，最少切割 3 次，将原串切割为“a”、“b”、“c”、“d”这四个回文子串。
 对于第三组样例，不需要切割，原串本身就是一个回文串。

40动态规划杂类