题目描述

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

一个长度为 $m$ 的字符串 $r$ 是回文的，当且仅当对所有 $1 \le i \le m$，都有：

例如 $aaabaaa$、$abba$ 是回文串，但 $aaabaa$ 不是。

给定一个字符串 $s$，将其划分为若干个非空子段，使得每一个子段都不是回文串，同时最大化划分出的子段数量。若无解则输出 $-1$。

子段定义为：从字符串中取一段连续字符形成的字符串。

由于字符串 $s$ 可能很长，我们采用 $(c, len)$ 的形式表示。

输入格式

从 rewrite.in 输入。

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

对于每组数据：

• 第一行一个整数 $n$，表示连续相同字符段的数量。
• 接下来 $n$ 行，每行包含一个字符 $c_i$（小写字母）和一个整数 $len_i$，表示该段字符及其长度。
• 保证对于所有 $i > 1$，有 $c_{i-1} \ne c_i$。

输出格式

向 rewrite.out 输出。

共 $T$ 行，每行一个整数，表示最大划分段数；若无解输出 $-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$
• 第 2 组：字符串为 $bbbb$，无合法方案
• 第 3 组：字符串为 $aabbabbaba$，可划分为 $aabb, ab, ba, ba$
• 第 4 组：字符串为 $aabaaccaa$，可划分为 $aaba, ac, caa$
• 第 5 组：字符串为 $aba$，无论如何划分都会出现回文子串

说明

更多样例详见 rewrite/rewrite*.in/ans 文件。

数据范围

• 数据点 1：$T = 10$，$1 \le n \le 3$，$1 \le len_i \le 2$
• 数据点 2：$T = 10$，$1 \le n \le 3$，$1 \le len_i \le 10^9$
• 数据点 3~4：$T = 10$，$1 \le n \le 150$，$1 \le len_i \le 2$
• 数据点 5~6：$T = 10$，$1 \le n \le 150$，$1 \le len_i \le 10^9$
• 数据点 7~9：$T = 10$，$1 \le n \le 10^3$，$1 \le len_i \le 2$
• 数据点 10~12：$T = 10$，$1 \le n \le 10^3$，$1 \le len_i \le 10^9$
• 数据点 13~16：$T = 10$，$1 \le n \le 10^5$，$1 \le len_i \le 2$
• 数据点 17~20：$T = 10$，$1 \le n \le 10^5$，$1 \le len_i \le 10^9$