2.3 Kristina's Burles

Score: 10pts

Time Limit: 5.00 sec

Kristina has a string of characters, which consists of both lowercase and uppercase Latin letters. She can earn "burles" by forming pairs of lowercase and uppercase of same letters in the string. Each pair counts as one burle. However, she is allowed to perform a limited number of operations on the string, where she can either convert a lowercase letter to uppercase or an uppercase letter to lowercase. She wants to maximize the number of burles she can earn.

Write a program to help Kristina determine the maximum number of burles she can earn for each given string and a specified limit on operations.

Write a program to help Kristina determine the maximum number of burles she can earn for each given string and a specified limit on operations.

Constraints

1 ≤ t ≤ 10^4

1 ≤ n ≤ 2 × 10^5

0 ≤ k ≤ n

1 ≤ n ≤ 2 × 10^5

0 ≤ k ≤ n

Input Format

- The first line contains an integer, `t` , which represents the number of test cases.

For each test case:

- The first line contains two integers, `n` and `k` , where `n` is the length of the string and `k` is the maximum number of operations Kristina can perform.

- The second line 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 × 10^5.

For each test case:

- The first line contains two integers, `n` and `k` , where `n` is the length of the string and `k` is the maximum number of operations Kristina can perform.

- The second line 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 × 10^5.

Output Format

For each test case, output a single integer on a separate line, which represents the maximum number of burles Kristina can earn for the given string and the specified limit on operations.

Example 1

Input:

5

11 2

aAaaBACacbE

2 2

ab

4 1

aaBB

6 0

abBAcC

5 3

cbccb

Output:

5

0

1

3

2

Explanation:

For 1 testcase , when k = 2 and s = "aAaaBACacbE" it can perform one operation: choose s3 = "a" and make it uppercase. Then she will get another pair of s3 = "A" and s8 = "a"

In the second test case, it is not possible to get any pair by performing any number of operations.

5

11 2

aAaaBACacbE

2 2

ab

4 1

aaBB

6 0

abBAcC

5 3

cbccb

Output:

5

0

1

3

2

Explanation:

For 1 testcase , when k = 2 and s = "aAaaBACacbE" it can perform one operation: choose s3 = "a" and make it uppercase. Then she will get another pair of s3 = "A" and s8 = "a"

In the second test case, it is not possible to get any pair by performing any number of operations.