You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

Lets say, an alphabetical substring is a substring of a string which starts from any character and followed by the next character of alphabet in the form "abcd...xyzabc...xyzabc...."
Note, this repeats in cyclic manner. See the testcases for more clarification

for example: some alphabetical substring from the string "cbcdtabyzabc" is "c","bcd","ab","yzabc"

You are given a string \(S\) of length \(N\) and an integer \(K\). You can make at most \(K\) replacement operation in the string.
In each replacement operation you can replace any character of string \(S\) to any other character.

Find the length of the maximum alphabetical substring of \(S\) after perfoming no more than \(K\) replacement operation.

String \(B\) is a substring of string \(A\) if \(B\) can be obtained from \(A\) by deleting several character from the leftmost side and rightmost side of \(A\).

Input

first line of input takes an integer \(T\) : number of testcases
first line of each testcase takes two integer \(N,K\) : size of the string, number of operation
second line of each testcase takes a string \(S\) of size \(N\)
\(1 <= T <= 10^4\)
\(1 <= N <= 10^5\)
\(0 <= K <= N\)

sum of \(N\) over all testcase will not exceed \(10^5\)

Output

One integer in each of the \(T\) line : Length of the maximum alphabetical subarray

Sample

4
6 2
azzzef
6 3
azzzef
10 5
apybtuezgb
10 5
ypybtuezgb

4
6
8
9

in the first testcase:
replace 3rd and 4th character by 'c' and 'd' we get "azcdef". the maximum length alphabetical substring is "cdef"

in the second testcase :
replace the string as "abcdef" and the maximum length alphabetical substring is "abcdef"

in the third testcase :
replace the string as "azabcdefgb" and the maximum length alphabetical substring is "zabcdefg""

in the fourth testcase :
replace the string as "yzabcdefgb" and the maximum length alphabetical substring is "yzabcdefg"