← 返回题目列表

Codeforces · 1907/C

C. 删除不吸引人的配对

中文机器翻译题面 查看原题

Vlad 发现了一个由 $$$n$$$ 小写拉丁字母组成的字符串 $$$s$$$,他想让它尽可能短。

为此,他可以多次从 $$$s$$$ 中删除任何一对相邻字符,只要它们不同。例如,如果$$$s$$$=racoon,那么通过删除一对字符,他可以获得字符串coon、roon、raon和raco,但他无法获得racn(因为删除的字母相同)或rcon(因为删除的字母不相邻)。

Vlad 通过应用任意数量的删除可以达到的最小长度是多少?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个数字 - 删除具有不同值的相邻字符对后字符串 $$$s$$$ 的最小长度。

示例

输入 #1

10
4
aabc
5
abaca
10
avbvvcvvvd
7
abcdefg
5
dabbb
8
aacebeaa
7
bbbbacc
6
dacfcc
6
fdfcdc
9
dbdcfbbdc

输出 #1

0
1
2
1
1
0
1
0
0
1

注意

在示例的第一个测试用例中,您需要执行以下操作:“aabc”$$$\rightarrow$$$“ac”$$$\rightarrow$$$“”。请注意,使用不同的删除顺序,字符串不会变空。