311275: CF1959C. Count the Number of Pairs

C. Count the Number of Pairstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Kristina has a string $s$ of length $n$, consisting only of lowercase and uppercase Latin letters. For each pair of lowercase letter and its matching uppercase letter, Kristina can get $1$ burl. However, pairs of characters cannot overlap, so each character can only be in one pair.

For example, if she has the string $s$ = "aAaaBACacbE", she can get a burl for the following character pairs:

• $s_1$ = "a" and $s_2$ = "A"
• $s_4$ = "a" and $s_6$ = "A"
• $s_5$ = "B" and $s_{10}$ = "b"
• $s_7$= "C" and $s_9$ = "c"

Kristina wants to get more burles for her string, so she is going to perform no more than $k$ operations on it. In one operation, she can:

• either select the lowercase character $s_i$ ($1 \le i \le n$) and make it uppercase.
• or select uppercase character $s_i$ ($1 \le i \le n$) and make it lowercase.

For example, when $k$ = 2 and $s$ = "aAaaBACacbE" it can perform one operation: choose $s_3$ = "a" and make it uppercase. Then she will get another pair of $s_3$ = "A" and $s_8$ = "a"

Find maximum number of burles Kristina can get for her string.

Input

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

The description of the test cases follows.

The first line of each test case contains two integers $n$ ($1 \le n \le 2 \cdot 10^5$) and $k$ ($0 \le k \le n$) — the number of characters in the string and the maximum number of operations that can be performed on it.

The second line of each test case contains a string $s$ of length $n$, consisting only of lowercase and uppercase 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, print exactly one integer on a separate line: the maximum number of burles that Kristina can get for her string $s$.

ExampleInput

5
11 2
aAaaBACacbE
2 2
ab
4 1
aaBB
6 0
abBAcC
5 3
cbccb

Output

5
0
1
3
2

Note

The first test case is explained in the problem statement.

In the second test case, it is not possible to get any pair by performing any number of operations.

题目大意：
克里斯蒂娜有一个长度为n的字符串s，由小写和大写拉丁字母组成。对于每一对大小写字母相同的字母，克里斯蒂娜可以得到1个布尔（burl）。但是，字符对不能重叠，因此每个字符只能在一个对中。克里斯蒂娜可以通过对字符串进行不超过k次操作来获得更多的布尔。每次操作可以选择一个小写字母并将其变为大写，或者选择一个大写字母并将其变为小写。需要找出克里斯蒂娜能为她的字符串获得的最大布尔数。

输入数据格式：
第一行输入一个整数t（1≤t≤10^4），表示测试用例的数量。
接下来是t个测试用例的描述。
每个测试用例的第一行包含两个整数n（1≤n≤2×10^5）和k（0≤k≤n），分别表示字符串的长度和可以进行的最大操作数。
每个测试用例的第二行包含一个长度为n的字符串s，由小写和大写拉丁字母组成。
保证所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出一行，包含一个整数，表示克里斯蒂娜可以为她的字符串s获得的最大布尔数。

例：
输入：
```
5
11 2
aAaaBACacbE
2 2
ab
4 1
aaBB
6 0
abBAcC
5 3
cbccb
```
输出：
```
5
0
1
3
2
```题目大意： 克里斯蒂娜有一个长度为n的字符串s，由小写和大写拉丁字母组成。对于每一对大小写字母相同的字母，克里斯蒂娜可以得到1个布尔（burl）。但是，字符对不能重叠，因此每个字符只能在一个对中。克里斯蒂娜可以通过对字符串进行不超过k次操作来获得更多的布尔。每次操作可以选择一个小写字母并将其变为大写，或者选择一个大写字母并将其变为小写。需要找出克里斯蒂娜能为她的字符串获得的最大布尔数。 输入数据格式： 第一行输入一个整数t（1≤t≤10^4），表示测试用例的数量。 接下来是t个测试用例的描述。 每个测试用例的第一行包含两个整数n（1≤n≤2×10^5）和k（0≤k≤n），分别表示字符串的长度和可以进行的最大操作数。 每个测试用例的第二行包含一个长度为n的字符串s，由小写和大写拉丁字母组成。 保证所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一行，包含一个整数，表示克里斯蒂娜可以为她的字符串s获得的最大布尔数。 例： 输入： ``` 5 11 2 aAaaBACacbE 2 2 ab 4 1 aaBB 6 0 abBAcC 5 3 cbccb ``` 输出： ``` 5 0 1 3 2 ```