B. Count the Number of Pairs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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$$$.

Example
Input
5
11 2
aAaaBACacbE
2 2
ab
4 1
aaBB
6 0
abBAcC
5 3
cbccb
Output
5
0
1
3
2
Note

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.