你发现你的一个朋友已经开始玩暴走P的 Master 谱面了，这时你打算做点坏事。 你找出了朋友的一个长度为 的音游打击序列，为了简化模型，这个序列只有 （命中）和 （不命中）。 下面定义音游打击序列每个位置的当前连击数： 有一个累加器，初始值设为 。 将序列从左到右依次扫描，对于当前某个字符，若它是 ，那么累加器加 ，否则累加器重置为 。 序列每个位置的当前连击数，等于扫描过这个位置后累加器的值。 例如，对于音游打击序列 ，每个位置的当前连击数依次是 。 整个音游打击序列的分数，等于打击序列每个位置的当前连击数之和。例如，对于音游打击序列 ，分数等于 。 现在你有 次动手脚的机会，每次机会可以将这个打击序列的一个 修改为 。 次机会可以全部使用、部分使用或完全不使用。你想知道所有修改方案中，分数的最小值可以是多少。

输入描述:

    每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：    第一行，输入两个正整数 代表序列的长度和机会的次数。    第二行，输入一个长度为 的字符串，保证出现的字符只会是 或 。    对于同一个测试点，保证所有数据的 之和不超过 。

输出描述:

    对于每组数据，输出一行一个整数，表示所有修改方案中，分数的最小值可以是多少。