CF1800B.Count the Number of Pairs

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.

克里斯蒂娜有一个长度为 $n$ 的字符串 $s$，其中仅包含小写和大写的拉丁字母。对于每一对小写字母及其对应的大写字母，克里斯蒂娜可以获得 $1$ 个“burle”（布勒）。但字符对之间不能重叠，即每个字符最多只能参与一个配对。

例如，若她拥有字符串 $s =$ "aAaaBACacbE"，则她可为以下字符对获得 burle：

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

为了从该字符串中获取更多 burle，克里斯蒂娜将对其执行至多 $k$ 次操作。每次操作可选择以下之一：

• 选取一个小写字母 $s_i$（$1 \le i \le n$），将其改为大写字母；
• 或选取一个大写字母 $s_i$（$1 \le i \le n$），将其改为小写字母。

例如，当 $k = 2$ 且 $s =$ "aAaaBACacbE" 时，她可执行一次操作：选取 $s_3 =$ "a" 并将其改为大写。之后她便能得到新的配对：$s_3 =$ "A" 和 $s_8 =$ "a"。

求克里斯蒂娜能从该字符串中获得的 burle 的最大数量。

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$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$（$1 \le n \le 2 \cdot 10^5$）和 $k$（$0 \le k \le n$）—— 字符串的长度以及可在该字符串上执行的最大操作次数。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写和大写拉丁字母组成。

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

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$.

对于每个测试用例，在单独一行中精确输出一个整数：Kristina 为其字符串 $s$ 能获得的最大 burles 数量。

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.

第一个测试用例在题目描述中已作解释。

在第二个测试用例中，无论执行多少次操作，都无法得到任何数对。