小苯的字符串染色

题号：NC287374
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小苯有个长度为 $n$ 的字符串 $S$ ，其中有一些字符是白色的，其余的都是黑色。

现在小苯需要对字符串进行恰好 $k$ 次染色，具体的染色操作：
$\bullet$ 选择一个没有选择过的下标 $1 \leq i \leq n$ ，接着将 $S_i$ 染成反色，即如果原本是白色，则染黑；原本是黑色，则染白。

染完色后，小苯会找在 $S$ 中找一个尽可能长的纯色子串，他想知道这个纯色子串的最大长度是多少，请你帮他算一算吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行两个正整数 ，分别表示  的长度，以及小苯要染色的次数。
第二行一个长度为  的  串表示 。（ 则表示白色， 表示黑色。）
（保证所有测试数据中， 的总和不超过 。）

输出描述:

对于每组测试数据，在单独的一行输出一个整数，表示染色完后  中最长连续纯色子串的长度。

示例1

输入

复制

输出

复制

3
3
1

说明

对于第三组测试数据，注意由于要染色的位置必须不同，因此必须将所有字符都染一次，则  变为：。
其中最长连续纯色子串长度是 。

备注:

纯色子串：即  中一段连续的子串，满足这个子串中所有字符颜色都相同。