快要小学毕业的小可可决定给好朋友小果果送毕业礼物。
现在小可可有一个长度为 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 行，每行一个正整数，表示这组数据的答案。

【样例 1 解释】

对于第一组测试数据，可以分割为 czc 和 cc。 对于第二组测试数据，可以分割为 a, b, aba 或 aba, b, a。

【样例 2 \sim 7】

见选手目录下的 string/string*.in 与 string/string*.ans。

样例中的 c 代表这组样例对应的实际测试点，其数据范围一致。

【数据范围】

下文中 N 表示单组测试点中所有测试数据 n 的总和。

对于所有测试数据，均有输入的数字均为正整数， t \le 100，n \le 5 × 10^6，N \le 1 × 10^7 且串 S 仅包含小写字母。

测试点信息

特殊性质说明

• 性质 A：满足 S 全为字符 a
• 性质 B：满足 S 中不存在任意两个相邻字母相同
• 性质 C：满足 S 随机生成，且 t = 2

“科大国创杯”2026 年安徽省青少年信息学科普日活动 小学组

科大国创杯