题目描述

Kristina 有一个长度为 $n$ 的字符串 $s$，该字符串只包含小写和大写拉丁字母。对于每一对小写字母及其对应的大写字母，Kristina 可以获得 $1$ 个 burl。然而，字符对不能重叠，所以每个字符只能属于一个对。

例如，如果她有字符串 $s = \text{"aAaaBACacbE"}$，她可以通过以下字符对获得 burl：

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

Kristina 想让她的字符串获得更多的 burl，因此她打算对字符串进行不超过 $k$ 次操作。每次操作，她可以：

• 选择一个小写字符 $s_i$（$1 \le i \le n$），并将其变为大写。
• 或者选择一个大写字符 $s_i$（$1 \le i \le n$），并将其变为小写。

例如，当 $k = 2$ 且 $s = \text{"aAaaBACacbE"}$ 时，她可以进行一次操作：选择 $s_3 = \text{"a"}$ 并将其变为大写。然后她可以再获得一对 $s_3 = \text{"A"}$ 和 $s_8 = \text{"a"}$。

请你求出 Kristina 能为她的字符串 $s$ 获得的最大 burl 数。

输入格式

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

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

每个测试用例的第一行包含两个整数 $n$（$1 \le n \le 2 \times 10^5$）和 $k$（$0 \le k \le n$），分别表示字符串的长度和最多可以进行的操作次数。

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

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

输出格式

对于每个测试用例，输出一行，包含一个整数，表示 Kristina 能为她的字符串 $s$ 获得的最大 burl 数。

说明/提示

第一个测试用例的解释见题目描述。

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

由 ChatGPT 4.1 翻译

样例

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

5
0
1
3
2