B4323 [科大国创杯小学组 2025] 改写

Subtask 0 为民间数据（最后两组测试点为民间 hack 数据），Subtask 1 为官方数据。

小可可在学习字符串算法！ 一个长度为 $m$ 的字符串 $r$ 是回文的，当且仅当 $r_i = r_{m+1-i}$ 对所有 $1 \leq i \leq m$ 均成立。例如 $\tt{aaabaaa}$，$\tt{abba}$ 都是回文串，但 $\tt{aaabaa}$ 不是回文串。 给定一个字符串 $s$，把 $s$ 分成若干个非空子段，使得每一个子段都不是回文的，同时最大化划分出的子段数目，请你输出最大划分数，无解则输出 $-1$。 子段的定义为：一个字符串保留任意连续字符后形成的字符串。 由于字符串 $s$ 可能很长，我们将会按照 $c, len$ 的形式给出整个字符串，具体含义见输入格式。

第一行一个整数 $T$ 表示数据组数。 对于每组数据，第一行输入一个数 $n$ 表示极长连续相同字母段的数量。 接下来 $n$ 行中，第 $i$ 行包括一个 $a$ 到 $z$ 之间的小写字母 $c_i$ 和一个整数 $len_i$，分别表示该段的数字以及长度，保证对于所有大于 $1$ 的 $i$，均满足 $c_{i-1} \neq c_i$。

输出共 $T$ 行，每行输出一个整数，表示最大的划分段数，若无解则输出 $-1$。

### 样例解释 - 对于第一组数据，序列为 $\tt{ba}$，且只存在 $\tt{ba}$ 这一种划分方案，因此答案为 $1$。 - 对于第二组数据，序列为 $\tt{bbbb}$，显然没有合法方案。 - 对于第三组数据，序列为 $\tt{aabbabbaba}$，存在一种划分出四段的方案: $\tt{aabb}$，$\tt{ab}$，$\tt{ba}$，$\tt{ba}$，可以证明没有答案更优的划分方式。 - 对于第四组数据，序列为 $\tt{aabaaccaa}$，存在一种划分出三段的方案: $\tt{aaba}$，$\tt{ac}$，$\tt{caa}$，可以证明没有答案更优的划分方式。 - 对于第五组数据，序列为 $\tt{aba}$，容易发现无论怎么划分，都至少有一个回文串，所以无解。 ### 约定和数据范围 - 数据点 $1$，$T = 10$，$1 \leq n \leq 3$，$1 \leq len_i \leq 2$。 - 数据点 $2$，$T = 10$，$1 \leq n \leq 3$，$1 \leq len_i \leq 10^9$。 - 数据点 $3, 4$，$T = 10$，$1 \leq n \leq 150$，$1 \leq len_i \leq 2$。 - 数据点 $5, 6$，$T = 10$，$1 \leq n \leq 150$，$1 \leq len_i \leq 10^9$。 - 数据点 $7 \sim 9$，$T = 10$，$1 \leq n \leq 2.5 \times 10^3$，$1 \leq len_i \leq 2$。 - 数据点 $10 \sim 12$，$T = 10$，$1 \leq n \leq 2.5 \times 10^3$，$1 \leq len_i \leq 10^9$。 - 数据点 $13 \sim 16$，$T = 10, 1 \leq n \leq 10^5, 1 \leq len_i \leq 2$。 - 数据点 $17 \sim 20$，$T = 10, 1 \leq n \leq 10^5, 1 \leq len_i \leq 10^9$。