测试数据来自 system/1298

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　如果一个字符串从左往右看和从右往左看完全相同的话，那么就认为这个串是一个回文串。例如，“abcaacba”是一个回文串，“abcaaba”则不是一个回文串。
　　如果一个字符串不是回文串，我们可以通过对字符串分割，使得分割完之后得到的所有子串都是回文的。那么一个给定的字符串，最少要分割多少次就可以达到目的。
　　例如，对于字符串“abaacca”，最少分割一次，就可以得到“aba”和“acca”这两个回文子串。

【输入格式】

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

【输出格式】

　　对于每组数据，输出一行。该行包含一个整数，表示最少分割的次数。

【输入输出样例】

　Input

3
abaacca
abcd
abcba

　Output

1
3
0

【输入输出样例解释】

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

【数据限制】

　　\(100\%\) 的数据满足，\(T ≤ 20\)，字符串长度不超过的 1000 。

【来源】

　　Mr.he