{"raw_statement":[{"iden":"background","content":"Subtask 0 为民间数据（最后两组测试点为民间 hack 数据），Subtask 1 为官方数据。"},{"iden":"statement","content":"小可可在学习字符串算法！\n\n一个长度为 $m$ 的字符串 $r$ 是回文的，当且仅当 $r_i = r_{m+1-i}$ 对所有 $1 \\leq i \\leq m$ 均成立。例如 $\\tt{aaabaaa}$，$\\tt{abba}$ 都是回文串，但 $\\tt{aaabaa}$ 不是回文串。\n\n给定一个字符串 $s$，把 $s$ 分成若干个非空子段，使得每一个子段都不是回文的，同时最大化划分出的子段数目，请你输出最大划分数，无解则输出 $-1$。\n\n子段的定义为：一个字符串保留任意连续字符后形成的字符串。\n\n由于字符串 $s$ 可能很长，我们将会按照 $c, len$ 的形式给出整个字符串，具体含义见输入格式。"},{"iden":"input","content":"第一行一个整数 $T$ 表示数据组数。\n\n对于每组数据，第一行输入一个数 $n$ 表示极长连续相同字母段的数量。\n\n接下来 $n$ 行中，第 $i$ 行包括一个 $a$ 到 $z$ 之间的小写字母 $c_i$ 和一个整数 $len_i$，分别表示该段的数字以及长度，保证对于所有大于 $1$ 的 $i$，均满足 $c_{i-1} \\neq c_i$。"},{"iden":"output","content":"输出共 $T$ 行，每行输出一个整数，表示最大的划分段数，若无解则输出 $-1$。"},{"iden":"note","content":"### 样例解释\n\n- 对于第一组数据，序列为 $\\tt{ba}$，且只存在 $\\tt{ba}$ 这一种划分方案，因此答案为 $1$。\n- 对于第二组数据，序列为 $\\tt{bbbb}$，显然没有合法方案。\n- 对于第三组数据，序列为 $\\tt{aabbabbaba}$，存在一种划分出四段的方案: $\\tt{aabb}$，$\\tt{ab}$，$\\tt{ba}$，$\\tt{ba}$，可以证明没有答案更优的划分方式。\n- 对于第四组数据，序列为 $\\tt{aabaaccaa}$，存在一种划分出三段的方案: $\\tt{aaba}$，$\\tt{ac}$，$\\tt{caa}$，可以证明没有答案更优的划分方式。\n- 对于第五组数据，序列为 $\\tt{aba}$，容易发现无论怎么划分，都至少有一个回文串，所以无解。\n\n### 约定和数据范围\n\n- 数据点 $1$，$T = 10$，$1 \\leq n \\leq 3$，$1 \\leq len_i \\leq 2$。\n- 数据点 $2$，$T = 10$，$1 \\leq n \\leq 3$，$1 \\leq len_i \\leq 10^9$。\n- 数据点 $3, 4$，$T = 10$，$1 \\leq n \\leq 150$，$1 \\leq len_i \\leq 2$。\n- 数据点 $5, 6$，$T = 10$，$1 \\leq n \\leq 150$，$1 \\leq len_i \\leq 10^9$。\n- 数据点 $7 \\sim 9$，$T = 10$，$1 \\leq n \\leq 2.5 \\times 10^3$，$1 \\leq len_i \\leq 2$。\n- 数据点 $10 \\sim 12$，$T = 10$，$1 \\leq n \\leq 2.5 \\times 10^3$，$1 \\leq len_i \\leq 10^9$。\n- 数据点 $13 \\sim 16$，$T = 10, 1 \\leq n \\leq 10^5, 1 \\leq len_i \\leq 2$。\n- 数据点 $17 \\sim 20$，$T = 10, 1 \\leq n \\leq 10^5, 1 \\leq len_i \\leq 10^9$。"}],"translated_statement":null,"sample_group":[["5\n2\nb 1\na 1\n1\nb 4\n7\na 2\nb 2\na 1\nb 2\na 1\nb 1\na 1\n5\na 2\nb 1\na 2\nc 2\na 2\n3\na 1\nb 1\na 1","1\n-1\n4\n3\n-1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}