310907: CF1907C. Removal of Unattractive Pairs

C. Removal of Unattractive Pairstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Vlad found a string $s$ consisting of $n$ lowercase Latin letters, and he wants to make it as short as possible.

To do this, he can remove any pair of adjacent characters from $s$ any number of times, provided they are different. For example, if $s$=racoon, then by removing one pair of characters he can obtain the strings coon, roon, raon, and raco, but he cannot obtain racn (because the removed letters were the same) or rcon (because the removed letters were not adjacent).

What is the minimum length Vlad can achieve by applying any number of deletions?

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line of each test case contains the string $s$ consisting of $n$ lowercase Latin letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single number—the minimum length of the string $s$, after removing pairs of adjacent characters with different values.

ExampleInput

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

Output

0
1
2
1
1
0
1
0
0
1

Note

In the first test case of the example, you need to act as follows: "aabc" $\rightarrow$ "ac" $\rightarrow$ "". Note that with a different order of deletions, the string will not become empty.

题目大意：
弗拉德发现了一个由n个小写拉丁字母组成的字符串s，并希望使它尽可能短。为了做到这一点，只要相邻字符不同，他就可以从s中删除任意一对相邻字符任意多次。例如，如果s=racoon，那么通过删除一对字符，他可以得到字符串coon，roon，raon和raco，但他不能得到racn（因为删除的字母相同）或rcon（因为删除的字母不相邻）。通过应用任意次数的删除，弗拉德可以实现字符串s的最小长度是多少？

输入数据格式：
第一行输入一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——字符串s的长度。
每个测试用例的第二行包含一个由n个小写拉丁字母组成的字符串s。
保证所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出一个数字——删除相邻的不同字符对后字符串s的最小长度。

示例：
输入：
```
10
4
aabc
5
abaca
10
avbvvcvvvd
7
abcdefg
5
dabbb
8
aacebeaa
7
bbbbacc
6
dacfcc
6
fdfcdc
9
dbdcfbbdc
```
输出：
```
0
1
2
1
1
0
1
0
0
1
```

注意：
在示例的第一个测试用例中，需要按以下步骤操作："aabc" -> "ac" -> ""。请注意，如果删除的顺序不同，字符串不会变空。题目大意： 弗拉德发现了一个由n个小写拉丁字母组成的字符串s，并希望使它尽可能短。为了做到这一点，只要相邻字符不同，他就可以从s中删除任意一对相邻字符任意多次。例如，如果s=racoon，那么通过删除一对字符，他可以得到字符串coon，roon，raon和raco，但他不能得到racn（因为删除的字母相同）或rcon（因为删除的字母不相邻）。通过应用任意次数的删除，弗拉德可以实现字符串s的最小长度是多少？ 输入数据格式： 第一行输入一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——字符串s的长度。 每个测试用例的第二行包含一个由n个小写拉丁字母组成的字符串s。 保证所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一个数字——删除相邻的不同字符对后字符串s的最小长度。 示例： 输入： ``` 10 4 aabc 5 abaca 10 avbvvcvvvd 7 abcdefg 5 dabbb 8 aacebeaa 7 bbbbacc 6 dacfcc 6 fdfcdc 9 dbdcfbbdc ``` 输出： ``` 0 1 2 1 1 0 1 0 0 1 ``` 注意： 在示例的第一个测试用例中，需要按以下步骤操作："aabc" -> "ac" -> ""。请注意，如果删除的顺序不同，字符串不会变空。