Codeforces Round 855 (Div. 3) |
---|
Finished |
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:
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:
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.
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$$$.
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$$$.
511 2aAaaBACacbE2 2ab4 1aaBB6 0abBAcC5 3cbccb
5 0 1 3 2
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.
Name |
---|