Largest Substring with At Most K Distinct Characters

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

In mathematical terms, if we denote a substring by s[i:j] (inclusive), you need to find $$\max_{0 \le i \le j < n} \{ j - i + 1 \}\quad \text{subject to}\quad |\{ s[x] : i \le x \le j \}| \le k,$$ where \(n\) is the length of the string and \(|\cdot|\) denotes the cardinality of the set.

The solution can be efficiently implemented using the sliding window technique.

inputFormat

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

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

outputFormat

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

## sample

5
eceba 2
aa 1
abcabcabc 2
aabbcc 2
ababab 2

3
2
2
4
6

</p>