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
注意
第一个测试用例在问题陈述中进行了解释。
在第二个测试用例中,不可能通过执行任意数量的操作来获得任何对。