A72019 | 好串串（string）

快要小学毕业的小可可决定给好朋友小果果送毕业礼物。
现在小可可有一个长度为 n 的小写字符串 S。

规定“好串串”是指前一半字典序单调不降，后一半字典序单调不升的回文串。
形式化地，长度为 m 的“好串” S 满足：

• S_1 \le S_2 \le ... \le S_{⌈m/2⌉}，S_{⌈m/2⌉} \ge S_{⌈m/2⌉+1} \ge ... \ge S_m；
• 对于所有 i = 1, 2, ..., m，满足 S_i = S_{m-i+1}；
• 注：字典序是指小写字母表中的顺序（a 最小 z 最大）；⌈m/2⌉ 表示 m/2 上取整。

如 z，bbb，accgcca，ccdeeedcc，ghg 等是“好串”，acbca，syzzh，ccb 等不是“好串”。

现在小可可要把 S 分割成若干个不相交的“好串”送给小果果。
因为小果果不想让书包里堆满“好串”，所以小可可要让分割出的“好串”个数尽量少。

可是小可可不会分割，请你来告诉她最少能分割成多少个“好串”吧！

本题多组测试。
从文件 string.in 中读取数据。

第一行两个正整数 C, t，表示测试点编号和数据组数，对于样例 1 满足 C = 0。

接下来 t 行，每行一个小写字符串 S，表示小可可的字符串。

输出到文件 string.out 中。

输出包含 t 行，每行一个正整数，表示这组数据的答案。