Longest Substring with At Most K Distinct Characters

You are given a string s and an integer k. Your task is to determine the length of the longest contiguous substring of s that contains at most k distinct characters.

More formally, consider a substring s[i:j] (where 0 \le i \le j \le n) such that the number of unique characters in s[i:j] is at most k. You are to find the maximum possible value of j-i among all such substrings. This can be written as:

$$\max_{0 \le i \le j \le n} \{j-i \mid |\{ s[i:j] \}| \le k\} $$

Use an efficient algorithm (such as a sliding window approach) to solve the problem.

inputFormat

The first line of the input contains an integer T, representing the number of test cases. Each test case consists of two lines:

• The first line contains a non-empty string s (without spaces).
• The second line contains an integer k, the maximum number of distinct characters permitted in the substring.

It is guaranteed that the input satisfies the constraints of the problem.

outputFormat

For each test case, output a single line containing one integer, which is the length of the longest substring that contains at most k distinct characters.

## sample

3
araaci
2
araaci
1
cbbebi
3

4
2
5

</p>