题目描述

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

一个长度为 $m$ 的字符串 $r$ 是回文的，当且仅当 $r_i = r_{m+1−i}$ 对所有 $1 ≤ i ≤ m$ 均成立。例如 $aaabaaa$, $abba$ 都是回文串，但 $aaabaa$ 不是回文串。

给定一个字符串 $s$，把 $s$ 分成若干个非空子段，使得每一个子段都不是回文的，同时最大化划分出的子段数目，请你输出最大划分数，无解则输出 −1。

子段的定义为：一个字符串保留任意连续字符后形成的字符串。

由于字符串 $s$ 可能很长，我们将会按照 $c, len$ 的形式给出整个字符串，具体含义见输入格式。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每组数据，第一行输入一个数 $n$ 表示极长连续相同字母段的数量。

接下来 $n$ 行中，第 $i$ 行包括一个 $a$ 到 $z$ 之间的小写字母 $c_i$ 和一个整数 $len_i$，分别表示该段的数字以及长度，保证对于所有大于 $1$ 的 $i$，均满足 c_{i−1} ̸= c_i。

输出格式

输出共 $T$ 行，每行输出一个整数，表示最大的划分段数，若无解则输出 $−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
4
3
-1

样例1解释

对于第一组数据，序列为 ba，且只存在 ba 这一种划分方案，因此答案为 1。

对于第二组数据，序列为 bbbb，显然没有合法方案。

对于第三组数据，序列为 aabbabbaba，存在一种划分出四段的方案：aabb,ab,ba,ba，可以证明没有答案更优的划分方式。

对于第四组数据，序列为 aabaaccaa，存在一种划分出三段的方案：aaba,ac,caa，可以证明没有答案更优的划分方式。

对于第五组数据，序列为 aba，容易发现无论怎么划分，都至少有一个回文串，所以无解。

约定和数据范围

数据点 $1$，$T = 10$, $1 ≤ n ≤ 3$, $1 ≤ len_i ≤ 2$。

数据点 $2$，$T = 10$, $1 ≤ n ≤ 3$, $1 ≤ len_i ≤ 10^9$。

数据点 $3, 4$，$T = 10$, $1 ≤ n ≤ 150$, $1 ≤ len_i ≤ 2$。

数据点 $5, 6$，$T = 10$, $1 ≤ n ≤ 150$, $1 ≤ len_i ≤ 10^9$。

数据点 $7 ∼ 9$，$T = 10$, $1 ≤ n ≤ 2.5 × 10^3$ , $1 ≤ len_i ≤ 2$。

数据点 $10 ∼ 12$，$T = 10$, $1 ≤ n ≤ 2.5 × 10^3$ , $1 ≤ len_i ≤ 10^9$。

数据点 $13 ∼ 16$，$T = 10$, $1 ≤ n ≤ 10^5$ , $1 ≤ len_i ≤ 2$。

数据点 $17 ∼ 20$，$T = 10$, $1 ≤ n ≤ 10^5$ , $1 ≤ len_i ≤ 10^9$。

ex_rewrite1.in  ex_rewrite1.ans

ex_rewrite2.in  ex_rewrite2.ans

ex_rewrite3.in  ex_rewrite3.ans

ex_rewrite4.in  ex_rewrite4.ans