段学长有一个长度为n的字符串s，仅由小写和大写拉丁字母组成。对于每一对小写字母和它匹配的大写字母，段学长可以得到1个积分。但是，字符对不能重叠，因此每个字符只能在一对中。
例如，如果她有字符串s = "aAaaBACacbE"，她可以得到以下字符对的
s1 = "a" and s6 = "A" and s5 = "B" and s10 = "b" and s7= "C" and s9 = "c"
此外段学长还有一中魔术，可以进行k次，可以将任意一个字符的大小写互换
例如，当k = 2并且s = "aAaaBACacbE"时，它可以执行一个操作:选择s3 = "a"并使其为大写。然后她会得到另一对s3 = "A"和s8 = "a"
找出克里斯汀娜的线绳能得到的最大积分数。

一个整数t表示总共有多少组样例
两个整数n，k分别表示字符串的长度，和可以使用魔法的次数
一行字符串

段学长可以获得最大的积分

1
11 2
aAaaBACacbE

5