← 返回题目列表

Codeforces · 1800/B

B. 计算对数

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

Kristina 有一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含小写和大写拉丁字母。对于每对小写字母及其匹配的大写字母,Kristina 可以得到 $$$1$$$ burl。但是,字符对不能重叠,因此每个字符只能位于一对中。

例如,如果她有字符串 $$$s$$$ = "aAaaBACacbE",她可以获得以下字符对的树节:

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

Kristina 希望为她的字符串获取更多的 burles,因此她不会对其执行超过 $$$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"

找出 Kristina 的绳子可以得到的最大节数。

输入

输入数据的第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,在单独的行上打印一个整数:Kristina 可以从她的字符串 $$$s$$$ 获得的最大 burles 数。

示例

输入 #1

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

输出 #1

5
0
1
3
2

注意

第一个测试用例在问题陈述中进行了解释。

在第二个测试用例中,不可能通过执行任意数量的操作来获得任何对。