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.

Formally, given a string \( S \) and an integer \( K \), you need to determine the maximum length \( L \) such that there exists a substring \( S[i \ldots j] \) (with \( 0 \le i \le j < |S| \)) where the number of distinct characters is at most \( K \). If \( K = 0 \), then the result is \( 0 \).

The input consists of multiple test cases. For each test case, you are provided with an integer K and a string S in a single line. You should output the answer for each test case on a new line.

inputFormat

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

T
K1 S1
K2 S2
... 
KT ST

Where:

• T is an integer denoting the number of test cases.
• Each of the next T lines contains an integer K and a string S separated by a space.

outputFormat

For each test case, output an integer on a separate line representing the length of the longest substring of S which contains at most K distinct characters. The output is printed to standard output (stdout).

## sample

3
2 abcba
1 aaabb
3 abcabcbb

3
3
8

</p>