题目描述
著名诗人、音乐家奥菲斯为了悼念他逝去的故友塞伯勒斯，为其创作了一首非常独特的诗，它只包含小写字母。现在邀请你一起来欣赏！
我们称一首诗所代表的字母序列的子串为回文，当且仅当它从前往后读和从后往前读相同。比如aba,aa,abba都是回文子串。
如果可以通过从开头的删除几个(可能为0或全部)字符，从结尾删除几个(可能为0或全部)字符，从序列A中得到B，则称B为A的一个子串。
那么现在给你很多很多句奥菲斯的诗，请判断其是否是回文序列。
以上和easy verson均相同
噫嘘唏,在欣赏完奥菲斯为其故友写的诗后，cbyyx和iheadx两位学长深深的被奥菲斯怀念其故友的情感所触动。
但是塞伯勒斯并不喜欢长度大于1的回文子串，比如在abaab这首诗中，他不喜欢aba,aa这些个回文子串。
由于两位学长还深陷其中，所以急需你的帮助：
你可以选择任意一个位置，将其替换为任意一个字符。你可以进行这种操作任意次。你要在尽可能少的操作次数下使这首诗不包含任意长度大于1的回文子串。
输入
多组测试样例。
第一行一个整数T，代表有T(T<= 100)组测试样例输入。
第2行，到第T+1行每行一个长度为m的字符串S，m<= 2000。
输出
对于每组测试样例，输出一个整数n。
代表你可以在最少n次操作下使其不包含任意长度大于1的回文子串。
7
babba
abaac
jangyi
zeroorez
abcdcba
bbbbbbb
a