Sorting the Pieces - Repovive Starter Round 7 | Repovive

21F. Sorting the Pieces

3000 pts2s256 MB

You are given a string $s$ consisting of lowercase English letters and an integer $k$ .

You may choose at most $k$ pairwise disjoint substrings of $s$ . For each chosen substring, independently rearrange its characters into nondecreasing alphabetical order.

Your goal is to make the entire string $s$ sorted in nondecreasing alphabetical order.

Find the minimum possible sum of the lengths of the chosen substrings. If $s$ is already sorted, you may choose no substrings, with a total length of $0$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le k \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$s$ consists only of lowercase English letters

Input

The first line contains the number of test cases $t$ .

Each test case is given in the following format:

\left. \begin{array}{l} n \quad k \\ s \end{array} \right\} \times t

Output

For each test case, output one integer: the minimum possible sum of the lengths of the chosen substrings.

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

9 1
bacdehgfi

Case 2

9 2
bacdehgfi

Explanation

Case 1

Sorting positions $1$ through $8$ produces the sorted string abcdefghi, with total length $8$ . The letters at positions $1$ and $2$ must exchange places, and so must the letters at positions $6$ and $8$ . With only one chosen substring, it has to cover all positions from $1$ through $8$ .

Case 2

Sort the substring at positions $1$ through $2$ and the substring at positions $6$ through $8$ . Their total length is $2+3=5$ , and every position that changes is covered.

Output

Case 1

Case 2

Input

Case 1

5 2
edcba

Case 2

14 2
bacdgfehijknml

Case 3

14 3
bacdgfehijknml

Explanation

Case 1

Sorting the whole string gives abcde, with cost $5$ . The letters a and e have to move between the two ends, so no shorter chosen substring can be sufficient.

Case 2

Sort positions $1$ through $7$ and positions $12$ through $14$ . The resulting string is abcdefghijklmn, and the total length is $7+3=10$ . With only two substrings, at least two of the three separated unsorted parts must be covered together; joining the first two has the smallest cost.

Case 3

Sort positions $1$ through $2$ , positions $5$ through $7$ , and positions $12$ through $14$ . These substrings have total length $2+3+3=8$ and make the whole string sorted.

Output

Case 1

Case 2

Case 3

You are given a string $s$ consisting of lowercase English letters and an integer $k$ .

You may choose at most $k$ pairwise disjoint substrings of $s$ . For each chosen substring, independently rearrange its characters into nondecreasing alphabetical order.

Your goal is to make the entire string $s$ sorted in nondecreasing alphabetical order.

Find the minimum possible sum of the lengths of the chosen substrings. If $s$ is already sorted, you may choose no substrings, with a total length of $0$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le k \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$s$ consists only of lowercase English letters

The first line contains the number of test cases $t$ .

Each test case is given in the following format:

\left. \begin{array}{l} n \quad k \\ s \end{array} \right\} \times t

For each test case, output one integer: the minimum possible sum of the lengths of the chosen substrings.

\left. \begin{array}{l} ans \end{array} \right\} \times t

Sort the substring at positions $1$ through $2$ and the substring at positions $6$ through $8$ . Their total length is $2+3=5$ , and every position that changes is covered.

Sorting the whole string gives abcde, with cost $5$ . The letters a and e have to move between the two ends, so no shorter chosen substring can be sufficient.

Sort positions $1$ through $2$ , positions $5$ through $7$ , and positions $12$ through $14$ . These substrings have total length $2+3+3=8$ and make the whole string sorted.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

21F. Sorting the Pieces

Constraints

Input

Output

Samples

21F. Sorting the Pieces

Constraints

Input

Output

Samples