Longest Substring with 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 which contains at most k distinct characters.

The problem can be stated mathematically as follows:

Given a string \(s\) of length \(n\) and an integer \(k\), find the maximum value of \(r - l + 1\) such that the substring \(s[l..r]\) contains at most \(k\) distinct characters.

Note: If k is zero or the string is empty, the answer is 0.

Constraints:

• \(1 \le T \le 100\) where T is the number of test cases.
• \(0 \le k \le 100\)
• \(0 \le |s| \le 10^4\)

Example:

Input:
3
2 eceba
3 aa
2 abcabc
Output:
3
2
2

</p>

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer T, the number of test cases.
• Each of the following T lines contains an integer k and a string s separated by space.

outputFormat

For each test case, output one line: the length of the longest substring that contains at most k distinct characters.

The output is printed to stdout.

## sample

3
2 eceba
3 aa
2 abcabc

3
2
2

</p>