CF1800B Count the Number of Pairs

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: - $ s_1 $ = "a" and $ s_2 $ = "A" - $ s_4 $ = "a" and $ s_6 $ = "A" - $ s_5 $ = "B" and $ s_{10} $ = "b" - $ s_7 $ = "C" and $ s_9 $ = "c" 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: - either select the lowercase character $ s_i $ ( $ 1 \le i \le n $ ) and make it uppercase. - or select uppercase character $ s_i $ ( $ 1 \le i \le n $ ) and make it lowercase. 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 $ .

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.