题目描述

快要小学毕业的小可可决定给好朋友小果果送毕业礼物。

现在小可可有一个长度为 $n$ 的小写字符串 $S$。 规定“好串串”是指前一半字典序单调不降、后一半字典序单调不升的回文串。

形式化地，长度为 $m$ 的“好串串” $S$ 满足： $S_1 \le S_2 \le \dots \le S_{\lceil \frac{m}{2} \rceil}$， $S_{\lceil \frac{m}{2} \rceil} \ge S_{\lceil \frac{m}{2} \rceil + 1} \ge \dots \ge S_m$； 对于所有 $i = 1, 2, \dots, m$，满足 $S_i = S_{m-i+1}$。

字典序是指小写字母表中的顺序（a 最小 z 最大）；$\lceil \frac{m}{2} \rceil$ 是指 $\frac{m}{2}$ 上取整。 如 z，bbb，accgcca，ccdeeedcc，ghg 等是“好串串”；acbca，syzzh，ccb 等不是“好串串”。

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

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

输入格式

本题多组测试。

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

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

输出格式

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

输入输出样例 #1

输入 #1

0 5
czccc
ababa
edffd
bbdddbb
aaababa

输出 #1

2
3
2
1
3

说明/提示

样例解释

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

数据范围

下文中 $N$ 表示单组测试点中所有测试数据 $n$ 的总和。 对于所有测试数据，均有输入的数字均为正整数， $t \le 100$，$n \le 5 \times 10^6$，$N \le 1 \times 10^7$ 且串 $S$ 仅包含小写字母。

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