Longest Substring with At Most K Distinct Characters

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

More formally, let the substring be denoted as s[i...j] (with 0-based indexing). You need to maximize j - i + 1 under the constraint that the number of distinct characters in s[i...j] does not exceed k. Mathematically, if we denote the set of distinct characters in s[i...j] by \(D(s[i...j])\), then you are to find:

[ \max_{0 \le i \le j < n} { j - i + 1 \ \text{ such that } |D(s[i...j])| \le k } ]

If k is 0, then the answer is 0 because no characters can be included.

inputFormat

The input is read from standard input.

The first line contains a single integer T denoting the number of test cases.

Each test case consists of two lines:

• The first line contains a non-negative string s (which may be empty).
• The second line contains an integer k representing the maximum number of distinct characters allowed.

It is guaranteed that 0 ≤ k ≤ |s| for each test case.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest substring of s that contains at most k distinct characters.

## sample

3
abcbae
2
aaaa
1
abacd
3

3
4
4

</p>