import sys

def solve():
    """
    Solves a single test case for the alphabetical substring problem.
    """
    try:
        # Read N (length of string) and K (max replacements)
        line1 = sys.stdin.readline()
        if not line1: return
        n, k = map(int, line1.split())
        
        # Read the string S
        s = sys.stdin.readline().strip()
    except (IOError, ValueError):
        # Handle potential empty lines or malformed input.
        return

    # 1. Transform the string S into an array of "base values".
    #    s_prime[i] = (ord(S[i]) - ord('a') - i) % 26
    s_prime = []
    for i in range(n):
        # Python's % operator handles negative results appropriately for this problem.
        # e.g., (0 - 2) % 26 = -2 % 26 = 24.
        val = (ord(s[i]) - ord('a') - i) % 26
        s_prime.append(val)

    global_max_len = 0

    # 2. Iterate through all 26 possible target base values.
    for target_val in range(26):
        # Use a sliding window to find the longest subarray that can be converted
        # to target_val with at most K replacements.
        left = 0
        cost = 0  # Number of replacements needed in the current window [left, right]

        for right in range(n):
            # Expand the window to the right.
            if s_prime[right] != target_val:
                cost += 1

            # If cost exceeds K, shrink the window from the left.
            while cost > k:
                # If the element being removed was a mismatch, decrement cost.
                if s_prime[left] != target_val:
                    cost -= 1
                left += 1

            # The current window [left, right] is valid. Update the max length.
            current_len = right - left + 1
            if current_len > global_max_len:
                global_max_len = current_len
    
    # 3. Print the final result.
    print(global_max_len)


def main():
    """
    Main function to handle multiple test cases.
    """
    try:
        num_test_cases_str = sys.stdin.readline()
        if not num_test_cases_str: return
        num_test_cases = int(num_test_cases_str)
        
        for _ in range(num_test_cases):
            solve()
    except (IOError, ValueError):
        # Handles cases where input is empty or malformed.
        pass

if __name__ == "__main__":
    main()