题目描述

小可可在学习字符串算法！

一个长度为 $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$。

输入输出样例 #1

输入 #1

5
2
b 1
a 1
1
b 4
7
a 2
b 2
a 1
b 2
a 1
b 1
a 1
5
a 2
b 1
a 2
c 2
a 2
3
a 1
b 1
a 1

输出 #1

1
-1
4
3
-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$。