Longest Substring with Same Character After K Operations

Given a string s consisting of lowercase English letters and an integer k, you are allowed to perform at most k operations on the string. In each operation, you may change any character to any other character. Your task is to determine the maximum possible length of a substring that contains only one repeated character after at most k changes.

The solution involves using a sliding window (two pointers) approach for each distinct character in the string. For each character, the window is expanded until more than k characters (that are different) are encountered, after which the window is contracted. The overall maximum over all characters is the answer.

For example, for the string "aabb" with k = 2, you can change the two b characters to a to obtain "aaaa", so the output is 4.

inputFormat

The first line of input contains an integer T representing the number of test cases.

Each of the following T lines contains a test case consisting of a string s and an integer k separated by a space.

Example:

3
 aabb 2
 abcde 1
 aaabbbcc 3

outputFormat

For each test case, output a single integer on a new line — the length of the longest substring that contains the same character after performing at most k operations.

## sample

3
aabb 2
abcde 1
aaabbbcc 3

4
2
6

</p>