A string is called a PANI string if all characters of the string are same. You are given a string S of length n. You can update k consecutive characters in the string to any characters. You have to find the maximum length of the PANI substring.

Constraints

$1 \leq t \leq 10^3$

$1 \leq n, k \leq 10^3$

$k \leq n$

String S contains only lower-case English alphabets (a...z).

Input Format

The first line contains t, number of test cases.

There will be two lines for each test case. The first line will contain ​​​ n and k and the second line will contain string S.

Output Format

Output t line. Each line contains a single integer equal to the maximum length of PANI substring.