Longest Substring with K Distinct Characters

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.

This problem can be stated mathematically as follows:

Find
$$ \max_{0 \leq i \leq j < n} \{ j - i + 1 \;|\; \text{the substring } s[i:j+1] \text{ contains at most } k \text{ distinct characters} \} $$

If k = 0, then the answer is 0 since no substring can contain 0 distinct characters.

Input is read from standard input and output is written to standard output.

inputFormat

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

Each test case consists of two lines:

• The first line contains the string s.
• The second line contains an integer k.

outputFormat

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

## sample

5
abcba
2
aaaa
1
aabacbebebe
3
eceba
2
abcba
0

3
4
7
3
0

</p>